結果

問題 No.3186 Big Order
ユーザー woshinailong
提出日時 2025-06-20 22:02:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,671 bytes
コンパイル時間 7,811 ms
コンパイル使用メモリ 399,756 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-20 22:02:52
合計ジャッジ時間 12,225 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13 TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/random/random_device.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int_distribution.hpp>

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;

const cpp_int MOD = 998244353;
const cpp_int ONE = 1;
const cpp_int TWO = 2;

cpp_int gcd(cpp_int a, cpp_int b) {
    while (b != 0) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

bool is_prime(const cpp_int& n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    cpp_int d = n - 1;
    int r = 0;
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }

    std::vector<long> bases = {2, 3, 5, 7, 11, 13, 17};
    for (long a : bases) {
        if (a >= n) continue;
        cpp_int x = mp::powm(cpp_int(a), d, n);
        if (x == 1 || x == n - 1) continue;

        bool composite = true;
        for (int i = 0; i < r - 1; i++) {
            x = mp::powm(x, TWO, n);
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

cpp_int f(const cpp_int& x, const cpp_int& c, const cpp_int& n) {
    return (x * x + c) % n;
}

cpp_int pollard_rho(const cpp_int& n, boost::random::mt19937_64& rng) {
    if (n % 2 == 0) return 2;
    if (n == 4) return 2;

    boost::random::uniform_int_distribution<cpp_int> dist(1, n - 1);
    for (int try_count = 0; try_count < 100; try_count++) {
        cpp_int x = dist(rng);
        cpp_int y = x;
        cpp_int c_val = dist(rng);
        cpp_int d = 1;

        for (int cycle = 1; d == 1; cycle++) {
            x = f(x, c_val, n);
            y = f(f(y, c_val, n), c_val, n);
            d = gcd(x > y ? x - y : y - x, n);

            if (d == n) break;
            if (d != 1) return d;
        }
    }
    return 0;
}

void factorize(cpp_int n, std::map<cpp_int, int>& factors) {
    if (n == 1) return;
    if (is_prime(n)) {
        factors[n]++;
        return;
    }
    if (n % 2 == 0) {
        int count = 0;
        while (n % 2 == 0) {
            count++;
            n /= 2;
        }
        factors[2] += count;
        factorize(n, factors);
        return;
    }

    static boost::random::mt19937_64 rng(std::time(0));
    cpp_int d = pollard_rho(n, rng);
    if (d == 0) {
        factors[n]++;
        return;
    }

    factorize(d, factors);
    factorize(n / d, factors);
}

int main() {
    std::srand(std::time(0));
    int T;
    std::cin >> T;

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

        if (A == 1) {
            std::cout << 0 << std::endl;
            continue;
        }

        std::map<cpp_int, int> factorC;
        factorize(C, factorC);

        bool found_zero = false;
        cpp_int k_min = -1;
        for (const auto& [p, e] : factorC) {
            int a_i = 0;
            cpp_int temp = A;
            while (temp % p == 0) {
                a_i++;
                temp /= p;
            }

            if (a_i == 0) {
                found_zero = true;
                break;
            }

            cpp_int k_i = (cpp_int(a_i) * B) / e;
            if (k_min == -1 || k_i < k_min) {
                k_min = k_i;
            }
        }

        if (found_zero) {
            std::cout << 0 << std::endl;
        } else {
            cpp_int res = k_min % MOD;
            std::cout << res << std::endl;
        }
    }

    return 0;
}
0