SRM 657 Div1 Medium PolynomialGCD

各素数ごとに独立になっているので、それぞれ解いて解を掛け合わせればよい。
素数 p の出現回数が一番多くなる場所を決めると、全体で何回 p が出現するかを O(NlogN/p) 程度で計算でき、場所の個数は、Nなので、各素数ごとに、O(N^2logN/p) で計算できる。
全体では、O(Nlog^2N) 程度で計算できる。

コーナーケースとして、s = "19592" のようなケースに注意する必要がある (1WA)
この例では、2 で 12 回割り切ることができる。 (一番左の 1 に 8 を割り当てるのが最適となるが、考察を間違えると、左右の 1 と 2 に 4 を割り当ててしまう。)

bool isPrime(ll x){
	if(x<=1) return false;
	for(ll i = 2; i*i <= x; i++) if(x%i==0) return false;
	return true;
}
ll pow_mod(ll a, ll r, ll m){
	ll x = 1;
	while(r){
		if(r&1) (x*=a)%=m;
		(a*=a)%=m;
		r>>=1;
	}
	return x;
}
 
class PolynomialGCD {
	public:
	int gcd(string s) {
		int n = s.size();
		vector<int> v(n);
		rep(i, n) v[i] = s[i]-'0';
		ll res = 1;
		for(ll i = 2; i <= n; i++){
			if(!isPrime(i)) continue;
			ll cnt = INF;
			for(ll j = 0; j < n; j++){
				ll c = 0, c2 = INF;
				ll x = i;
				while(c2>=i){
					c2 = 0;
					for(ll k = j%x; k < n; k += x) c += v[k], c2++;
					x *= i;
				}
				chmin(cnt, c);
			}
			(res*=pow_mod(i, cnt, mod))%=mod;
		}
		return res;
	}
};