結果

問題 No.3186 Big Order
ユーザー nouka28
提出日時 2025-06-21 01:17:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,042 bytes
コンパイル時間 9,845 ms
コンパイル使用メモリ 500,500 KB
実行使用メモリ 16,068 KB
最終ジャッジ日時 2025-06-21 01:17:58
合計ジャッジ時間 13,740 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;
const cpp_int MOD = 998244353;

// --- 乗算 (cpp_int はオーバーフローしないのでそのまま) ---
inline cpp_int mul_mod(const cpp_int& a, const cpp_int& b, const cpp_int& mod) {
    return (a * b) % mod;
}

// --- 素数判定（Miller–Rabin, deterministic for <= 2^128） ---
bool isPrime(const cpp_int& n) {
    static const uint64_t smallPrimes[] = {
        2,3,5,7,11,13,17,19,23,29,31,37
    };
    if (n < 2) return false;
    for (uint64_t p : smallPrimes) {
        if (n == p) return true;
        if (n % p == 0) return false;
    }

    // n-1 = d * 2^s
    cpp_int d = n - 1;
    unsigned s = 0;
    while ((d & 1) == 0) { d >>= 1; ++s; }

    auto check = [&](uint64_t a) -> bool {
        cpp_int x = boost::multiprecision::powm(cpp_int(a), d, n);
        if (x == 1 || x == n - 1) return true;
        for (unsigned r = 1; r < s; ++r) {
            x = mul_mod(x, x, n);
            if (x == n - 1) return true;
        }
        return false;
    };

    for (uint64_t a : smallPrimes) {
        if (a >= n) break;
        if (!check(a)) return false;
    }
    return true;
}

// --- Pollard–Rho ---
std::mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

cpp_int rho_f(const cpp_int& x, const cpp_int& c, const cpp_int& mod) {
    return (mul_mod(x, x, mod) + c) % mod;
}

cpp_int pollard(const cpp_int& n) {
    if ((n & 1) == 0) return 2;
    while (true) {
        cpp_int c = rng() % (n - 2) + 1;
        cpp_int x = rng() % (n - 2) + 2;
        cpp_int y = x;
        cpp_int d = 1;
        while (d == 1) {
            x = rho_f(x, c, n);
            y = rho_f(rho_f(y, c, n), c, n);
            cpp_int diff = x > y ? x - y : y - x;
            d = gcd(diff, n);
        }
        if (d != n) return d;
    }
}

// --- 再帰的因数分解 ---
void factor(cpp_int n, std::map<cpp_int,int>& res) {
    if (n == 1) return;
    if (isPrime(n)) { ++res[n]; return; }
    cpp_int d = pollard(n);
    factor(d, res);
    factor(n/d, res);
}

// --- v_p(A) を求める ---
int valuation(cpp_int a, const cpp_int& p) {
    int cnt = 0;
    while (a % p == 0) { a /= p; ++cnt; }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;  cin >> T;
    while (T--) {
        string sA, sB, sC; cin >> sA >> sB >> sC;
        cpp_int A(sA), B(sB), C(sC);

        // 素因数分解
        map<cpp_int,int> fac;
        factor(C, fac);

        cpp_int ans = cpp_int(-1);   // "∞" の代用
        bool zero = false;

        for (auto [p, e] : fac) {
            int f = valuation(A, p);     // f_i
            if (f == 0) { zero = true; break; }

            cpp_int tmp = cpp_int(f) * B;   // B * f_i
            cpp_int k = tmp / e;            // floor
            if (ans < 0 || k < ans) ans = k;
        }

        cpp_int out = (zero ? 0 : ans) % MOD;
        cout << out << '\n';
    }
    return 0;
}
0