結果

問題 No.2795 Perfect Number
コンテスト
ユーザー shobonvip
提出日時 2024-06-26 23:30:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 90 ms / 2,000 ms
コード長 1,857 bytes
コンパイル時間 377 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 76,288 KB
最終ジャッジ日時 2024-06-28 20:50:51
合計ジャッジ時間 3,199 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

# O(N^1/4 + Nの約数の個数×log N)

# https://judge.yosupo.jp/submission/90854
import random

def gcd(a, b):
	while a: a, b = b%a, a
	return b

def isprime(n):
	if n == 2: return 1
	if n == 1 or n%2 == 0: return 0
	m = n-1; lsb = m & -m; s = lsb.bit_length()-1; d = m//lsb
	if n < 4759123141: test_numbers = [2, 7, 61]
	elif n < 341550071728321: test_numbers = [2, 3, 5, 7, 11, 13, 17]
	elif n < 3825123056546413051: test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23]
	else: test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
	for a in test_numbers:
		if a == n:continue
		x = pow(a,d,n); r = 0
		if x == 1:continue
		while x != m:
			x = pow(x,2,n); r += 1
			if x == 1 or r == s:return 0
	return 1

def find_prime_factor(n):
	m = max(1,int(n**0.125))
	while True:
		c = random.randrange(n); y = k = 0; g = q = r = 1
		while g == 1:
			x = y; mr = 3*r//4
			while k < mr: y = (pow(y,2,n)+c)%n; k += 1
			while k < r and g == 1:
				ys = y
				for _ in range(min(m, r-k)): y = (pow(y,2,n)+c)%n; q = q*abs(x-y)%n
				g = gcd(q,n); k += m
			k = r; r <<= 1
		if g == n:
			g = 1; y = ys
			while g == 1: y = (pow(y,2,n)+c)%n; g = gcd(abs(x-y),n)
		if g == n:continue
		if isprime(g):return g
		elif isprime(n//g):return n//g
		else:return find_prime_factor(g)

def factorize(n):
	res = {}
	for p in range(2,1000):
		if p*p > n: break
		if n%p: continue
		s = 0
		while n%p == 0: n //= p; s += 1
		res[p] = s
	while not isprime(n) and n > 1:
		p = find_prime_factor(n); s = 0
		while n%p == 0: n //= p; s += 1
		res[p] = s
	if n > 1: res[n] = 1
	return res

n = int(input())
d = list(factorize(n).items())
ans = 0 
def dfs(i, j, k, use):
	global ans
	if use:
		ans += i
	if len(d) <= j: return
	if d[j][1] >= k + 1:
		dfs(i * d[j][0], j, k + 1, True)
	dfs(i, j+1, 0, False)
	return

dfs(1, 0, 0, 1)
if ans == n * 2:
	print("Yes")
else:
	print("No")
0