結果

問題 No.28 末尾最適化
ユーザー kimiyukikimiyuki
提出日時 2017-01-06 15:23:47
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 826 ms / 5,000 ms
コード長 2,204 bytes
コンパイル時間 1,006 ms
コンパイル使用メモリ 93,972 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-09 20:59:37
合計ジャッジ時間 2,204 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 826 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0