SRM657 Div1 Medium "PolynomialGCD"
考えたこと
公約数といえばやっぱり2^a * 3^b * 5^c + ... と素因数分解して考えればよさそう。素数(2, 3, 5, 7, 11...)ごとに、関数Pにその素数が最小何個含まれるかを計算できればよい。そのときに|s|より大きい素数は考える必要はない。理由としては以下のようにxを調整することで、その素数を素因数として持たない数列にすることができるから
で、計算なんだけど、数列の各数字には関数Pの式より乗数がかかる[x^2 * (x-1)^0 * (x - 2)^1 * (x - 4)^4とか]のでめんどくさい。あと各数字が素数pをいくつ持つかは規則性はあるもののバラバラ(p = 2なら、0102010301020104...とか)なので、これもめんどくさい。
例えば、p = 2では以下のように考えていく。
s = "251"とする。 P(x) = x^2 * (x-1)^5 * (x-2)^1 p = 2を考える。 連続した数列は、2つおきに2を素因数として持つので、パターンは2つ考えられる。 ■パターン1 1つ目の整数から使う 2 5 1 ^ ^ ■パターン2 2つ目の整数から使う 2 5 1 ^ ただし、パターン1の場合、 どちらかは素因数2を2つ持つ(2^2)ので、 さらに足す必要がある。 ■パターン1-a 2 5 1 2^1 ^ ^ 2^2 ^ ■パターン1-b 2 5 1 2^1 ^ ^ 2^2 ^ パターン1-a = 2 + 1 + 2 パターン1-b = 2 + 1 + 1(☆最小) パターン2 = 5 となり、 P(x) = x^2 * (x-1)^5 * (x-2)^1は約数2^4を持つことが保証される。
↑を再帰関数で求めていけばよい。
ソースコード
class PolynomialGCD { public: int N; string S; bool P[10050]; const long long MOD = 1000000007; int gcd(string s) { N = s.size(); S = s; memset(P, 1, sizeof(P)); long long ans = 1; for (int p = 2; p <= N; p++) { if (!P[p]) continue; // 素数pごとにP(x)に最低限どれだけ含まれるかを求めていく int t = solve(p, 1, 0); for (int i = 0; i < t; i++) { ans *= p; ans %= MOD; } // 素数ではないものを消していく for (int i = p + p; i <= N; i += p) { P[i] = false; } } return ans; } // P(x)にp * nが約数として最低限どれだけ含まれるかを返す // p...素数 // n... // o...オフセット(数列のどこから考えてる?) int solve(int p, int n, int o) { int res = MOD; for (int i = 0; i < p; i++) { int sum = 0; int c = 0; for (int j = o + i * n; j < N; j += n * p) { sum += S[j] - '0'; c++; } if (c >= p) { sum += solve(p, n * p, o + i * n); } res = min(res, sum); } return res; } };