yukicoder : No.2264 Gear Coloring

これはどうにか。
https://yukicoder.me/problems/no/2264

問題

N個の歯車が順にかみ合っている。
各歯車の歯の数が与えられる。

それぞれの歯を、M色のいずれかで塗り分けることを考える。
歯車を回転して一致する塗り方は同一視するとき、全体で塗り方は何通りか。

解法

各歯車の個数のLCMを求め、LCMの約数Dを総当たりして、

• 歯車を歯D個分回転させると初めて色が元に戻る塗り方

を考えよう。
これは「歯車を歯D個分回転させると色が元に戻る塗り方」から「歯車を歯D個未満かつDの約数分回転させると初めて色が元に戻る塗り方」を引けばよい。
前者は、Dが求められれば各歯車の色の塗り分け方が計算できる。
d(LCM)は高々1344なので後者をO(d(LCM)^2)掛けても十分間に合う。

int N,M;
ll A[1010];
const ll mo=998244353;

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;
	
	cin>>N>>M;
	ll L=1;
	FOR(i,N) {
		cin>>A[i];
		L=L*A[i]/__gcd(L,A[i]);
	}
	ll ret=0;
	vector<pair<ll,ll>> C;
	for(i=1;i*i<=L;i++) if(L%i==0) {
		C.push_back({i,0});
		if(i*i!=L) C.push_back({L/i,0});
	}
	sort(ALL(C));
	FORR2(g,v,C) {
		v=1;
		FOR(i,N) {
			x=__gcd(g,(ll)A[i]);
			(v*=modpow(M,x))%=mo;
		}
		FORR2(g2,v2,C) if(g2<g&&g%g2==0) v+=mo-v2;
		v%=mo;
		ret+=v*modpow(g)%mo;
	}
	cout<<ret%mo<<endl;
	
}

まとめ

最初無駄にポリアの数え上げ定理使おうとして頭が混乱した。