結果
問題 | No.2795 Perfect Number |
ユーザー |
![]() |
提出日時 | 2024-09-28 15:10:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 2,105 bytes |
コンパイル時間 | 349 ms |
コンパイル使用メモリ | 82,604 KB |
実行使用メモリ | 60,756 KB |
最終ジャッジ日時 | 2024-09-28 15:10:57 |
合計ジャッジ時間 | 2,643 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
def gcd(a, b):while a:a, b = b%a, areturn bdef is_prime(n):if n == 2:return 1if n == 1 or n%2 == 0:return 0m = n - 1lsb = m & -ms = lsb.bit_length()-1d = m // lsbtest_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]for a in test_numbers:if a == n:continuex = pow(a,d,n)r = 0if x == 1:continuewhile x != m:x = pow(x,2,n)r += 1if x == 1 or r == s:return 0return 1def find_prime_factor(n):if n%2 == 0:return 2m = int(n**0.125)+1for c in range(1,n):f = lambda a: (pow(a,2,n)+c)%ny = 0g = q = r = 1k = 0while g == 1:x = ywhile k < 3*r//4:y = f(y)k += 1while k < r and g == 1:ys = yfor _ in range(min(m, r-k)):y = f(y)q = q*abs(x-y)%ng = gcd(q,n)k += mk = rr *= 2if g == n:g = 1y = yswhile g == 1:y = f(y)g = gcd(abs(x-y),n)if g == n:continueif is_prime(g):return gelif is_prime(n//g):return n//gelse:return find_prime_factor(g)def factorize(n):res = {}while not is_prime(n) and n > 1: # nが合成数である間nの素因数の探索を繰り返すp = find_prime_factor(n)s = 0while n%p == 0: # nが素因数pで割れる間割り続け、出力に追加n //= ps += 1res[p] = sif n > 1: # n>1であればnは素数なので出力に追加res[n] = 1return resn=int(input())F=factorize(n)res=1for key,val in F.items():tmp=0while val:tmp+=pow(key,val)val-=1res*=tmp+1print('Yes' if res==2*n else 'No')