結果

問題 No.28 末尾最適化
ユーザー H3PO4H3PO4
提出日時 2023-03-30 10:05:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 342 ms / 5,000 ms
コード長 1,776 bytes
コンパイル時間 1,805 ms
コンパイル使用メモリ 99,280 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-21 21:30:46
合計ジャッジ時間 2,188 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>

int isqrt(int n) {
    int x = n;
    int y = (x + 1) / 2;
    while (y < x) {
        x = y;
        y = (x + n / x) / 2;
    }
    return x;
}

std::unordered_map<int, int> factorization(int n) {
    std::unordered_map<int, int> res;
    int tmp = n;
    const int sq_n = isqrt(n);
    for (int i = 2; i < sq_n + 1; ++i) {
        if (tmp % i == 0) {
            int cnt = 0;
            while (tmp % i == 0) {
                cnt += 1;
                tmp /= i;
            }
            res.emplace(i, cnt);
        }
    }
    if (tmp != 1) res.emplace(tmp, 1);
    if (res.empty() && n != 1) res.emplace(n, 1);

    return res;
}

int solve(int seed, int N, int K, int B) {
    std::vector<long long> X(N + 1);
    X.at(0) = seed;
    for (int i = 1; i < N + 1; ++i) {
        const auto &x = X.at(i - 1);
        X.at(i) = 1 + (x * x + x * 12345) % 100000009;
    }
    const auto f = factorization(B);
    int res = N;
    for (const auto &[k, v]: f) {
        std::vector<int> factor_count;
        for (const auto &x: X) {
            auto tmp = x;
            int cnt = 0;
            while (tmp % k == 0) {
                cnt++;
                tmp /= k;
            }
            factor_count.push_back(cnt);
        }
        std::sort(factor_count.begin(), factor_count.end());
        int cnt_sum = 0;
        for (int i = 0; i < K; ++i) {
            cnt_sum += factor_count.at(i);
        }
        if (res > (cnt_sum / v)) res = cnt_sum / v;
    }
    return res;
}

int main() {
    int Q;
    std::cin >> Q;
    for (int i = 0; i < Q; ++i) {
        int seed, N, K, B;
        std::cin >> seed >> N >> K >> B;
        std::cout << solve(seed, N, K, B) << std::endl;
    }
}
0