No.28 末尾最適化

No.28 末尾最適化 - yukicoder

• 問題をみた瞬間なんじゃこりゃーってなった問題。
• 解答をみると難しくはないとわかるけど。

class TailCallOptim {
public:
    void solve(void) {
            int Q;
            cin>>Q;

            REP(_,Q)
            {
                int seed, n,K,B;
                cin>>seed>>n>>K>>B;
                vector<ll> x(n+1);
                x[0] = seed;
                FOR(i,1,n+1)
                    x[i] = 1+(x[i-1]*x[i-1] + x[i-1]*12345 + 100000009) % 100000009;
                //
                // B を素因数分解する
                // B = P1^K1 * ... Pm^Km とする
                //
                // 一方 T = P1^L1 * ... Pm^Lm * S とすると
                //
                // T の B 進表現末尾 0 の個数は min { Li/Ki } となる
                //                              i
                // こいつを最小化すればよい
                int ans = (1<<30);
                auto primes = primeFactorize(B);
                // 各素数ごとに調べる
                for (auto pk : primes)
                {
                    int p,k;
                    tie(p,k) = pk;

                    vector<int> ks(n+1,0);
                    // 各 x の p^k の冪を求める
                    REP(i,n+1)
                    {
                        int l = 0;
                        ll  tmp = x[i];
                        while (tmp % p == 0)
                        {
                            ++l;
                            tmp /= p;
                        }
                        ks[i] = l;
                    }
                    sort(RANGE(ks));
                    int L = 0;
                    // L が小さくなるように ks を小さいものから K 個加算
                    REP(i,K)
                        L += ks[i];
                    ans = min(ans, L/k);// 最小値を更新
                }
                cout<<ans<<endl;
            }
    }
};