結果
問題 | No.1322 Totient Bound |
ユーザー | maspy |
提出日時 | 2020-12-19 15:07:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,528 ms / 5,000 ms |
コード長 | 2,575 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 81,816 KB |
実行使用メモリ | 89,472 KB |
最終ジャッジ日時 | 2023-10-21 09:14:14 |
合計ジャッジ時間 | 59,409 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
53,608 KB |
testcase_01 | AC | 40 ms
53,608 KB |
testcase_02 | AC | 40 ms
53,608 KB |
testcase_03 | AC | 40 ms
53,608 KB |
testcase_04 | AC | 39 ms
53,608 KB |
testcase_05 | AC | 40 ms
53,608 KB |
testcase_06 | AC | 40 ms
53,608 KB |
testcase_07 | AC | 40 ms
53,608 KB |
testcase_08 | AC | 43 ms
53,608 KB |
testcase_09 | AC | 40 ms
53,608 KB |
testcase_10 | AC | 40 ms
53,608 KB |
testcase_11 | AC | 40 ms
53,608 KB |
testcase_12 | AC | 39 ms
53,608 KB |
testcase_13 | AC | 123 ms
76,988 KB |
testcase_14 | AC | 123 ms
76,976 KB |
testcase_15 | AC | 101 ms
76,460 KB |
testcase_16 | AC | 111 ms
76,472 KB |
testcase_17 | AC | 101 ms
76,440 KB |
testcase_18 | AC | 763 ms
79,856 KB |
testcase_19 | AC | 1,110 ms
81,120 KB |
testcase_20 | AC | 2,613 ms
85,788 KB |
testcase_21 | AC | 2,877 ms
86,320 KB |
testcase_22 | AC | 2,882 ms
86,328 KB |
testcase_23 | AC | 3,508 ms
87,768 KB |
testcase_24 | AC | 3,502 ms
88,196 KB |
testcase_25 | AC | 3,524 ms
87,528 KB |
testcase_26 | AC | 3,528 ms
89,004 KB |
testcase_27 | AC | 3,487 ms
87,568 KB |
testcase_28 | AC | 3,490 ms
87,000 KB |
testcase_29 | AC | 3,487 ms
87,548 KB |
testcase_30 | AC | 39 ms
53,404 KB |
testcase_31 | AC | 39 ms
53,616 KB |
testcase_32 | AC | 39 ms
53,616 KB |
testcase_33 | AC | 3,482 ms
89,472 KB |
testcase_34 | AC | 3,410 ms
88,124 KB |
testcase_35 | AC | 3,484 ms
88,224 KB |
testcase_36 | AC | 3,420 ms
87,784 KB |
testcase_37 | AC | 3,404 ms
88,008 KB |
testcase_38 | AC | 3,437 ms
88,900 KB |
ソースコード
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 - 1 sum_hi[i] = N // i - 1 for p in range(2, sqN + 1): if sum_lo[p] == sum_lo[p - 1]: continue sp = sum_lo[p - 1] pp = p * p for i in range(1, sqN + 1): n = N // i if n < pp: break x = sum_hi[i * p] if i * p <= sqN else sum_lo[n // p] sum_hi[i] -= x - sp for n in range(sqN, pp - 1, -1): sum_lo[n] -= sum_lo[n // p] - sp return sum_lo, sum_hi def dfs(N, primes): # 値、どの素数まで使ったか stack = [(1,1,0)] while stack: n, phi, nxt_i = stack.pop() yield n, phi, nxt_i for i in range(nxt_i, len(primes)): p = primes[i] if phi * (p-1) * p > N: break phi_p = p - 1 n_p=p while True: if phi * phi_p * p > N: break stack.append((n*n_p, phi * phi_p, i+1)) phi_p *= p n_p*=p def main(N): pi_lo, pi_hi = prime_count(N) sqN = len(pi_lo) - 1 def 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 in memo: return memo[n] for p in primes: if p*p>n: break if n%p==0: memo[n]=False return False memo[n] = True return True primes = [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 = 1 for n, phi, nxt_i in dfs(N, primes): cnt = 0 # 2 乗以上をかける場合 MAX = N // phi for i in range(nxt_i, len(primes)): p = primes[i] k = 1 phi_p = (p-1) while phi_p * p <= MAX: k += 1 phi_p *= p if k == 1: break cnt += k - 1 # 素数をひとつかける場合。(p-1)phi <= N となる p に関する集計 # p - 1 <= N//phi。 k = pi(N//phi) if isprime(N//phi+1): k += 1 k -= nxt_i cnt += max(k, 0) ans += cnt return ans print(main(int(input())))