結果

問題 No.3186 Big Order
コンテスト
ユーザー jiangxinyang
提出日時 2025-06-20 21:59:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,111 bytes
コンパイル時間 6,452 ms
コンパイル使用メモリ 424,588 KB
実行使用メモリ 11,168 KB
最終ジャッジ日時 2025-06-20 22:00:17
合計ジャッジ時間 10,346 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 13 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
cpp_int mulmod(const cpp_int& a, const cpp_int& b, const cpp_int& mod) {
    return (a * b) % mod;
}
cpp_int powmod(cpp_int a, cpp_int e, const cpp_int& mod) {
    cpp_int r = 1;
    a %= mod;
    while (e > 0) {
        if ((e & 1) != 0) r = mulmod(r, a, mod);
        a = mulmod(a, a, mod);
        e >>= 1;
    }
    return r;
}
bool isPrime(const cpp_int& n) {
    if (n < 2) return false;
    for (int p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n == p) return true;
        if (n % p == 0) return false;
    }
    cpp_int d = n - 1;
    unsigned s = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }
    for (cpp_int a_base : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
        if (a_base % n == 0) continue;
        cpp_int x = powmod(a_base, d, n);
        if (x == 1 || x == n - 1) continue;
        bool composite = true;
        for (unsigned r = 1; r < s; r++) {
            x = mulmod(x, x, n);
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}
cpp_int pollard_rho(const cpp_int& n) {
    if (n % 2 == 0) return 2;
    if (n % 3 == 0) return 3;
    cpp_int c = cpp_int(rng() % 10000) + 1;
    cpp_int x = cpp_int(rng() % 10000) + 1;
    cpp_int y = x;
    cpp_int d = 1;
    auto f = [&](const cpp_int& v) { return (mulmod(v, v, n) + c) % n; };
    while (d == 1) {
        x = f(x);
        y = f(f(y));
        d = boost::multiprecision::gcd((x > y ? x - y : y - x), n);
    }
    return (d == n ? pollard_rho(n) : d);
}
void factor_rec(const cpp_int& n, map<cpp_int, int>& factors) {
    if (n == 1) return;
    if (isPrime(n)) {
        factors[n]++;
    } else {
        cpp_int d = pollard_rho(n);
        factor_rec(d, factors);
        factor_rec(n / d, factors);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const long long MOD = 998244353;
    int T;
    cin >> T;
    while (T--) {
        cpp_int A, B, C;
        cin >> A >> B >> C;
        map<cpp_int, int> fac;
        factor_rec(C, fac);
        cpp_int best_k;
        bool first = true;
        for (auto& it : fac) {
            const cpp_int& p = it.first;
            int e = it.second;
            cpp_int tmp = A;
            long long v = 0;
            while (tmp % p == 0) {
                tmp /= p;
                v++;
            }
            cpp_int k_i = (B * v) / e;
            if (first) {
                best_k = k_i;
                first = false;
            } else {
                if (k_i < best_k) best_k = k_i;
            }
        }
        long long ans = 0;
        for (; best_k > 0; best_k >>= 32) {
            unsigned long block = (unsigned long)(best_k & 0xFFFFFFFFu);
            ans = ((ans << 32) + block) % MOD;
        }
        cout << ans << "\n";
    }
    return 0;
}
0