AtCoder ARC #202 : C - Repunits

これ全然詰め切れなかった…。
https://atcoder.jp/contests/arc202/tasks/arc202_c

問題

N要素の整数列Aが与えられる。
R(n)を、n桁のレピュニット数とする。

LCM(R(A[0]),R(A[1]),....,R(A[k]))を、k=0～(N-1)に対し求めよ。

解法

となるようにすると、

となる。
F(n)は小さい順に計算すれば、R(n)から求めることができる。
また、LCMの値については、LCM(A_0,A_1,...,A_k)の約数として、1,2,3,...,200000が含まれるかを管理し、含まれるdにおけるF(d)の積を更新していけばよい。

int N;
ll A[202020];
const ll mo=998244353;

vector<int> cand[202020];
int M[202020];
ll F[202020];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=200000;i++) {
		for(j=i;j<=200000;j+=i) {
			cand[j].push_back(i);
		}
	}
	
	for(i=1;i<=200000;i++) {
		F[i]=modpow(10,i)-1;
		FORR(c,cand[i]) if(c<i) F[i]=F[i]*modpow(F[c])%mo;
	}
	
	cin>>N;
	ll cur=modpow(9);
	FOR(i,N) {
		int a;
		cin>>a;
		
		FORR(c,cand[a]) {
			if(M[c]==0) {
				M[c]=1;
				(cur*=F[c])%=mo;
			}
		}
		
		cout<<cur<<endl;
	}
	
}

まとめ

これは全く思い浮かばなかった…。