結果

問題 No.2798 Multiple Chain
コンテスト
ユーザー eve__fuyuki
提出日時 2024-07-09 13:45:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 4,648 bytes
コンパイル時間 2,024 ms
コンパイル使用メモリ 204,752 KB
最終ジャッジ日時 2025-02-22 02:35:28
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}
long long mul(long long a, long long b, long long mod) {
    long long res = (__int128_t)a * b % mod;
    return res;
}
long long pow_mod(long long a, long long b, long long mod) {
    __int128_t res = 1;
    __int128_t aa = a;
    while (b) {
        if (b & 1) {
            res = mul(res, aa, mod);
        }
        aa = mul(aa, aa, mod);
        b >>= 1;
    }
    return res;
}
class MillerRabin {
    vector<long long> tester = {2,      325,     9375,      28178,
                                450775, 9780504, 1795265022};

   public:
    bool is_prime(long long n) {
        long long s = 0, d;
        {
            long long tmp = n - 1;
            while (tmp % 2 == 0) {
                tmp /= 2;
                s++;
            }
            d = tmp;
        }
        for (long long a : tester) {
            if (a > n - 1) {
                continue;
            }
            long long base = pow_mod(a, d, n);
            if (base == 1) {
                continue;
            }
            bool flg = false;
            for (int r = 0; r < s; r++) {
                if (base == n - 1) {
                    flg = true;
                    break;
                }
                base = mul(base, base, n);
            }
            if (!flg) {
                return false;
            }
        }
        return true;
    }
};
class Pollard_rho {
    vector<long long> primes = {
        2,  3,  5,  7,  11, 13, 17, 19, 23, 29, 31, 37, 41,
        43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
    };

   public:
    long long findfactor(long long n) {
        MillerRabin mr;
        long long m = 1LL << (__builtin_clzll(n) / 8);
        for (long long c = 1; c < 99; c++) {
            auto f = [&](long long x) { return (mul(x, x, n) + c) % n; };
            long long y = 2, r = 1, q = 1, g = 1;
            long long x, ys;
            while (g == 1) {
                x = y;
                for (long long i = 0; i < r; i++) {
                    y = f(y);
                }
                long long k = 0;
                while (k < r && g == 1) {
                    ys = y;
                    for (long long i = 0; i < min(m, r - k); i++) {
                        y = f(y);
                        q = mul(q, abs(x - y), n);
                    }
                    g = gcd(q, n);
                    k += m;
                }
                r *= 2;
            }
            if (g == n) {
                while (true) {
                    ys = f(ys);
                    g = gcd(abs(ys - x), n);
                    if (g > 1) {
                        break;
                    }
                }
            }
            if (g < n) {
                if (mr.is_prime(g)) {
                    return g;
                } else if (mr.is_prime(n / g)) {
                    return n / g;
                } else {
                    return findfactor(g);
                }
            }
        }
        assert(false);
    };
    map<long long, int> factors(long long n) {
        map<long long, int> res;
        for (long long p : primes) {
            if (p * p > n) {
                break;
            }
            while (n % p == 0) {
                res[p]++;
                n /= p;
            }
        }
        while (n > 1) {
            if (MillerRabin().is_prime(n)) {
                res[n]++;
                break;
            }
            long long f = findfactor(n);
            while (n % f == 0) {
                res[f]++;
                n /= f;
            }
        }
        return res;
    }
};
int main() {
    fast_io();
    Pollard_rho pr;
    long long n;
    cin >> n;
    auto pf = pr.factors(n);
    vector<long long> sep_num = {
        1,       1,       2,       3,       5,       7,       11,      15,
        22,      30,      42,      56,      77,      101,     135,     176,
        231,     297,     385,     490,     627,     792,     1002,    1255,
        1575,    1958,    2436,    3010,    3718,    4565,    5604,    6842,
        8349,    10143,   12310,   14883,   17977,   21637,   26015,   31185,
        37338,   44583,   53174,   63261,   75175,   89134,   105558,  124754,
        147273,  173525,  204226,  239943,  281589,  329931,  386155,  451276,
        526823,  614154,  715220,  831820,  966467,  1121505, 1300156, 1505499,
        1741630, 2012558, 2323520, 2679689, 3087735, 3554345, 4087968};
    long long ans = 1;
    for (auto [p, cnt] : pf) {
        ans *= sep_num[cnt];
    }
    cout << ans << endl;
}
0