WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM657 Div1 Medium "PolynomialGCD"

考えたこと

公約数といえばやっぱり2^a * 3^b * 5^c + ... と素因数分解して考えればよさそう。素数(2, 3, 5, 7, 11...)ごとに、関数Pにその素数が最小何個含まれるかを計算できればよい。そのときに|s|より大きい素数は考える必要はない。理由としては以下のようにxを調整することで、その素数を素因数として持たない数列にすることができるから
f:id:Ekaing:20150524154734j:plain


で、計算なんだけど、数列の各数字には関数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;
    }
};