結果

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <set>
#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>
#include <boost/multiprecision/integer.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(const cpp_int& a, const cpp_int& b) {
    return mp::gcd(a, b);
}

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;

    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; cycle <= 10000; cycle++) {
            x = f(x, c_val, n);
            y = f(y, c_val, n);
            y = f(y, c_val, n);
            cpp_int diff = x > y ? x - y : y - x;
            d = gcd(diff, n);
            if (d != 1 && d != n) {
                return d;
            }
            if (d == n) {
                break;
            }
        }
    }
    return 0;
}

void factorize(cpp_int n, std::set<cpp_int>& factors) {
    if (n == 1) return;
    if (is_prime(n)) {
        factors.insert(n);
        return;
    }
    if (n % 2 == 0) {
        factors.insert(2);
        factorize(n / 2, factors);
        return;
    }

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

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

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(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 << '\n';
            continue;
        }

        cpp_int g = gcd(A, C);
        if (g == 1) {
            std::cout << 0 << '\n';
            continue;
        }

        std::set<cpp_int> primes;
        factorize(g, primes);

        bool first = true;
        cpp_int k_min;
        bool found_zero = false;

        for (cpp_int p : primes) {
            int a_i = 0;
            cpp_int temp = A;
            while (temp % p == 0) {
                a_i++;
                temp /= p;
            }

            int e_i = 0;
            temp = C;
            while (temp % p == 0) {
                e_i++;
                temp /= p;
            }

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

            cpp_int total = cpp_int(a_i) * B;
            cpp_int k_i = total / e_i;

            if (first) {
                k_min = k_i;
                first = false;
            } else if (k_i < k_min) {
                k_min = k_i;
            }
        }

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

    return 0;
}
0