結果

問題 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
0