题解：AT_arc202_c [ARC202C] Repunits

先是一个观察：

\gcd (R_x,R_y) = R_{\gcd(x,y)}

，正确性显然。

把

\operatorname{lcm}

反演了：

\begin{align*} \operatorname{lcm}(R_{a_1},R_{a_2},\dots ,R_{a_i}) & = \prod_{T \subseteq \{ R_{a_1},R_{a_2},\dots ,R_{a_i} \} } \gcd(T)^{(-1)^{|T|-1}} \\ & = \prod_{T \subseteq \{ a_1,a_2,\dots ,a_i \} } R_{\gcd(T)}^{(-1)^{|T|-1}}\\ \end{align*}

\gcd

很烦，将其转成有关因数的。设

R_n = \prod_{i | n} F_i

，则：

\begin{align*} & = \prod_{T \subseteq \{ a_1,a_2,\dots ,a_i \} } (\prod_{i | \gcd(T)} F_i ) ^{(-1)^{|T|-1}}\\ & = \ \prod_d \; F_d \times [\; \exists \; d \; | \; a_i \; ] \end{align*}

莫反求出

F

数组，然后就做完了。

CPP


/*

       2025.11.20

 * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef pair<int,int>P;
const int MAXN=200005,inf=0x3f3f3f3f3f3f3f3f,mod=998244353;
int n,a[MAXN],mu[MAXN],ff[MAXN],f[MAXN],R[MAXN],IR[MAXN],ans=1;
bool vis[MAXN];
vector<int>pri,p[MAXN];
int pw(int base,int t){
	int ans=1;
	while(t){
		if(t&1)ans=ans*base%mod;
		base=base*base%mod,t>>=1;
	}
	return ans;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    mu[1]=1;f[1]=1;
    for(int i=2;i<MAXN;i++){
    	f[i]=1;
    	if(!ff[i])pri.pb(i),mu[i]=-1;
    	for(int j:pri){
    		if(j*i>=MAXN)break;
    		ff[j*i]=1;
    		if(i%j==0){mu[i*j]=0;break;}
    		mu[i*j]=-mu[i];
		}
	}
	for(int i=1;i<MAXN;i++)R[i]=(R[i-1]*10+1)%mod,IR[i]=pw(R[i],mod-2);
	for(int i=1;i<MAXN;i++)for(int j=i;j<MAXN;j+=i){
		p[j].pb(i);
		if(mu[j/i]==1)f[j]=(f[j]*R[i])%mod;
		if(mu[j/i]==-1)f[j]=f[j]*IR[i]%mod;
	}
	for(int i=1;i<=n;i++){
		for(int j:p[a[i]])if(!vis[j])vis[j]=1,ans=ans*f[j]%mod;
		cout<<ans<<'\n';
	}
    return 0;
}

题解：AT_arc202_c [ARC202C] Repunits

文章操作

相关推荐

评论

题解：AT_arc202_c [ARC202C] Repunits