Yukicoder No.28 末尾最適化

,

http://yukicoder.me/problems/no/28

嘘のつもりで投げたら通り、実は正しい解法だった。だめ。

solution

$B$の素因数のどれがボトルネックになるか全部試す。$O(Q \cdot ( N_i\log N_i + B \log \log B))$。

$B = p_1^{k_1}p_2^{k_2}\dots p_l^{k_l}$とする。 $T = p_1^{k_1’}p_2^{k_2’}\dots p_l^{k_l’}R$としたとき、末尾の$0$の数$\mathrm{cnt} = \min_i \lfloor \frac{k_i’}{k_i} \rfloor$。 この$j = \operatorname{argmin}_i \lfloor \frac{k_i’}{k_i} \rfloor$を決め打ちすれば、$X$を(他の素数を考慮せず)単に$p_j$の指数の小さい方から$K$個掛け合わせて$T$とすればよくなる。

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
vector<int> sieve_of_eratosthenes(int n) { // enumerate primes in [2,n] with O(n log log n)
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i*i <= n; ++i)
        if (is_prime[i])
            for (int k = i+i; k <= n; k += i)
                is_prime[k] = false;
    vector<int> primes;
    for (int i = 2; i <= n; ++i)
        if (is_prime[i])
            primes.push_back(i);
    return primes;
}
map<int,int> prime_factrorize(int n, vector<int> const & primes) {
    map<int,int> result;
    for (int p : primes) {
        if (n < p * p) break;
        while (n % p == 0) {
            result[p] += 1;
            n /= p;
        }
    }
    if (n != 1) result[n] += 1;
    return result;
}
const int inf = 1e9+7;
int main() {
    int q; cin >> q;
    while (q --) {
        int seed, n, k, b; cin >> seed >> n >> k >> b;
        map<int,int> ps = prime_factrorize(b, sieve_of_eratosthenes(b));
        vector<vector<int> > xs;
        for (int x = seed; xs.size() < n+1; x = x *(ll) (x + 12345) % 100000009 + 1) {
            int y = x;
            xs.emplace_back();
            for (auto it : ps) {
                int p = it.first;
                xs.back().push_back(0);
                while (y % p == 0) { ++ xs.back().back(); y /= p; }
            }
        }
        int ans = inf;
        repeat (p,ps.size()) {
            partial_sort(xs.begin(), xs.begin() + k, xs.end(), [&](vector<int> const & x, vector<int> const & y) { return x[p] < y[p]; });
            vector<int> t(ps.size());
            repeat (i,k) repeat (j,ps.size()) t[j] += xs[i][j];
            int j = 0;
            for (auto it : ps) {
                int cnt = it.second;
                setmin(ans, t[j] / cnt);
                ++ j;
            }
        }
        cout << ans << endl;
    }
    return 0;
}