結果
問題 | No.2480 Sequence Sum |
ユーザー |
👑 |
提出日時 | 2023-09-23 02:02:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 42 ms / 500 ms |
コード長 | 1,859 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 58,240 KB |
最終ジャッジ日時 | 2024-07-26 14:41:47 |
合計ジャッジ時間 | 1,522 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 13 |
ソースコード
from math import gcddef isprime(n):if n <= 1:return Falseelif n == 2:return Trueelif n % 2 == 0:return FalseA = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]s = 0d = n - 1while d % 2 == 0:s += 1d >>= 1for a in A:if a % n == 0:return Truex = pow(a, d, n)if x != 1:for t in range(s):if x == n - 1:breakx = x * x % nelse:return Falsereturn Truedef pollard(n):if n % 2 == 0:return 2if isprime(n):return nf = lambda x: (x * x + 1) % nstep = 0while 1:step += 1x = stepy = f(x)while 1:p = gcd(y - x + n, n)if p == 0 or p == n:breakif p != 1:return px = f(x)y = f(f(y))def primefact(n):if n == 1:return []p = pollard(n)if p == n:return [p]left = primefact(p)right = primefact(n // p)left += rightreturn sorted(left)def primedict(n):P = primefact(n)ret = {}for p in P:ret[p] = ret.get(p, 0) + 1return retdef divisor_lst(n):if n == 1:return [1]primes = primefact(n)primes.append(primes[-1] + 1)bef = primes[0]cnt = 0ret = [1]for p in primes:if p == bef:cnt += 1else:times = befle = len(ret)for _ in range(cnt):for i in range(le):ret.append(ret[i] * times)times *= befbef = pcnt = 1ret.sort()return retn = int(input())print(n - len(divisor_lst(n)))