题解：AT_arc202_c [ARC202C] Repunits
FS_NEO
·
·
题解
先是一个观察：\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*}
$$
\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;
}
```