Yukicoder028 末尾最適化

問題概要

$X[0]=seed$
$X[n] = 1 + (X[n-1]^2 + 12345*X[n-1])\%100000009$
$(1≦n≦N)$
とする。 上の定義から作られる $N+1$ 個の要素を持つ数列 $X$ の中から $K$ 個数字を選びそれらを掛け合わせ $T$ とおく。 $T$ を$ B$ 進数に変換した時末尾の$0$の数が最小となる $T$ では末尾の$0$の数はいくつになるかという質問が$Q$与えられるので、それぞれ回答えよ。

$1≦Q≦10^3、seed≦100000009、N≦10^4、K≦N+1、2≦B≦36$

yukicoder028

解法

最終的に選択した積の要素に含まれる$B$を構成する素因数の個数が最小になるようになっていればよい。
したがって$B = 2^{b[2]} * 3^{b[3]} *5^{b[5]} * …$のうち、$T$を作成した際にできる$T$の素因数である$Tb[i]$ を比較して、すべての素因数から$min(Tb[i]/b[i])$ となるように数を選択すればよい。
これがよいことの証明をふんわりと示す。
ある素因数を一つ決めてこれを最小にしようとする。 貪欲に集めたが、そうでないものが最適であったとする。
このとき、どれか別の素因数が最小となっているため、全部の素因数について探索すればよいことになる。
これすき。

計算量:$O(Q(N\sqrt B+B(NlogN+K)))$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using VI = vector<int>;       using VVI = vector<VI>;
    using VL = vector<LL>;        using VVL = vector<VL>;
    #define ALL(a)  begin((a)),end((a))
    #define SORT(c) sort(ALL((c)))
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    const int INF = 1e9;                          const LL LINF = 1e16;
    
    LL N;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        int Q;  cin >> Q;
        const LL mod = 100000009;
        FOR(q, 0, Q) {
    
            LL seed, N, K, B;
            cin >> seed >> N >> K >> B;
            LL BB = B;
            VI b(B + 1, 0);
            for (int i = 2; i*i <= BB; i++) {
                while (B%i == 0) {
                    b[i]++;
                    B /= i;
                }
            }
            if (B != 1) {
                b[B]++;
            }
            VL x(N + 1);
            x[0] = seed;
            FOR(i, 1, N + 1) {
                x[i] = 1 + (x[i - 1] * x[i - 1] + x[i - 1] * 12345) % mod;
            }
    
            B = BB;
            VVI bx(B + 1, VI(N + 1, 0));
            //VVI xb(N + 1, VI(B + 1, 0));
            FOR(i, 0, N + 1) {
                for (int j = 2; j <= B; j++) {
                    if (b[j])while (x[i] % j == 0) {
                        bx[j][i]++;
                        x[i] /= j;
                    }
                }
            }
    
            int ans = INF;
            FOR(i, 2, B + 1) {
                if (b[i]) {
                    int Base = b[i];
                    sort(bx[i].begin(), bx[i].end());
                    int ret = 0;
                    FOR(k, 0, K) {
                        ret += bx[i][k];
                    }
                    ans = min(ans, ret / Base);
                }
            }
    
            cout << ans << "\n";
        }
    
        return 0;
    }