結果

問題 No.2795 Perfect Number
ユーザー lingfunny
提出日時 2024-06-28 21:30:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,829 bytes
コンパイル時間 3,154 ms
コンパイル使用メモリ 255,492 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-28 21:31:14
合計ジャッジ時間 3,772 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using LLL = __int128;
const int primes[] = {1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 20, 31, 37};
inline LL qpow(LL x, LL k, LL mod) {
    LL res = 1;
    while(k) {
        if(k&1) res = (LLL)res*x%mod;
        x = (LLL)x*x%mod;
        k >>= 1;
    }
    return res;
}
inline bool millerRabin(LL x) {
    if(x < 2 || !(x&1)) return x==2;
    LL d = x-1; int t = 0;
    while(!(d&1)) d>>=1, ++t;
    for(int i=1, j;i<=12;++i) {
        if(x == primes[i]) return true;
        if(x%primes[i] == 0 || qpow(primes[i], x-1, x) != 1) return false;
        LL u = qpow(primes[i]%x, d, x);
        if(u == 1) continue;
        for(j=0;j<t;++j) {
            if(u == x-1) break;
            u = (LLL)u*u%x;
        }
        if(j >= t) return false;
    }
    return true;
}
inline LL gcd(LL x, LL y) {
    if(x < y) swap(x, y);
    while(y) {
        x %= y;
        swap(x, y);
    }
    return x;
}
inline LL f(LL x, LL c, LL mod) { return ((LLL)x*x+c)%mod; }
std::mt19937_64 rrand(114514);
inline LL pollardRho(LL x) {
    LL s = 0, t = 0, val, c = rrand()%(x-1)+1;
    for(int goal = 1; ; goal <<= 1, s = t) {
        val = 1;
        for(int step = 1; step <= goal; ++step) {
            t = f(t, c, x);
            val = (LLL)val * abs(t-s) % x;
            if(!(step%127)) {
                LL d = gcd(val, x);
                if(d > 1) return d;
            }
        }
        LL d = gcd(val, x);
        if(d > 1) return d;
    }
}
map <LL, int> M;
void fac(LL n) {
    if(millerRabin(n) || n <= 2) {
        if (n > 1) M[n] += 1;
        return;
    }
    LL x = n;
    while(x == n) x = pollardRho(n); 
    fac(x), fac(n / x);
}
vector<pair<LL, int>> fact;
LL n, s;
int tot;
void dfs(int i, LL cur) {
    if (i == tot) {
        s += cur;
        return;
    }
    auto [p, c] = fact[i];
    for (LL j = 0, x = 1; j <= c; ++j, x *= p)
        dfs(i + 1, cur * x);
}
int main() {
    cin >> n;
    fac(n);
    for (auto [p, c] : M) fact.emplace_back(p, c);
    tot = fact.size();
    dfs(0, 1);
    puts(s == 2 * n ? "Yes" : "No");
    return 0;
}
// pollard_rho
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0