結果
問題 | No.1322 Totient Bound |
ユーザー |
![]() |
提出日時 | 2020-12-19 15:10:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,517 ms / 5,000 ms |
コード長 | 2,703 bytes |
コンパイル時間 | 309 ms |
コンパイル使用メモリ | 82,192 KB |
実行使用メモリ | 89,960 KB |
最終ジャッジ日時 | 2024-09-21 10:19:29 |
合計ジャッジ時間 | 57,867 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
def prime_count(N):""" O(N^{0/75}) で、 pi(N//i) を列挙する。"""sqN = int(N**.5)sum_lo = [0] * (sqN+1)sum_hi = [0] * (sqN+1)for i in range(1, sqN + 1):sum_lo[i] = i - 1sum_hi[i] = N // i - 1for p in range(2, sqN + 1):if sum_lo[p] == sum_lo[p - 1]:continuesp = sum_lo[p - 1]pp = p * pfor i in range(1, sqN + 1):n = N // iif n < pp:breakx = sum_hi[i * p] if i * p <= sqN else sum_lo[n // p]sum_hi[i] -= x - spfor n in range(sqN, pp - 1, -1):sum_lo[n] -= sum_lo[n // p] - spreturn sum_lo, sum_hidef dfs(N, primes):# 値、どの素数まで使ったかstack = [(1,1,0)]while stack:n, phi, nxt_i = stack.pop()yield n, phi, nxt_ifor i in range(nxt_i, len(primes)):p = primes[i]if phi * (p-1) * p > N:breakphi_p = p - 1n_p=pwhile True:if phi * phi_p * p > N:breakstack.append((n*n_p, phi * phi_p, i+1))phi_p *= pn_p*=pdef main(N):pi_lo, pi_hi = prime_count(N)sqN = len(pi_lo) - 1def pi(x):if x <= sqN:return pi_lo[x]return pi_hi[N//x]memo = dict()def isprime(n):if n <= sqN:return pi_lo[n] > pi_lo[n-1]if n == 2:return Trueif n in memo:return memo[n]if pow(2, n-1, n) != 1:memo[n] = Falsereturn Falsefor p in primes:if p*p>n:breakif n%p==0:memo[n]=Falsereturn Falsememo[n] = Truereturn Trueprimes = [p for p in range(2, sqN+1) if pi_lo[p] > pi_lo[p-1]]if isprime(sqN+1):primes.append(sqN+1)ans = 1 # N = 1for n, phi, nxt_i in dfs(N, primes):cnt = 0# 2 乗以上をかける場合MAX = N // phifor i in range(nxt_i, len(primes)):p = primes[i]k = 1phi_p = (p-1)while phi_p * p <= MAX:k += 1phi_p *= pif k == 1:breakcnt += k - 1# 素数をひとつかける場合。(p-1)phi <= N となる p に関する集計# p - 1 <= N//phi。k = pi(N//phi)if isprime(N//phi+1):k += 1k -= nxt_icnt += max(k, 0)ans += cntreturn ansprint(main(int(input())))