結果
問題 |
No.1322 Totient Bound
|
ユーザー |
![]() |
提出日時 | 2025-04-16 15:54:15 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,793 bytes |
コンパイル時間 | 273 ms |
コンパイル使用メモリ | 81,856 KB |
実行使用メモリ | 86,216 KB |
最終ジャッジ日時 | 2025-04-16 15:55:40 |
合計ジャッジ時間 | 7,641 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 TLE * 1 -- * 25 |
ソースコード
def is_prime(n): if n <= 1: return False elif n <= 3: return True elif n % 2 == 0: return False d = n - 1 s = 0 while d % 2 == 0: d //= 2 s += 1 for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]: if a >= n: continue x = pow(a, d, n) if x == 1 or x == n - 1: continue for _ in range(s - 1): x = pow(x, 2, n) if x == n - 1: break else: return False return True def count_totient_bound(N): total = 0 def count_exponents(primes, R): if not primes: return 1 p = primes[0] rest = primes[1:] count = 0 current = 1 while True: if current > R: break count += count_exponents(rest, R // current) current *= p return count def generate_subsets(current_primes, current_product, last_prime): nonlocal total if current_product > N: return R = N // current_product cnt = count_exponents(current_primes, R) total += cnt remaining = N // current_product p_start = last_prime + 1 p_end = remaining + 1 p = p_start while p <= p_end: if is_prime(p): d = p - 1 if d > remaining: break new_product = current_product * d if new_product > N: p += 1 continue generate_subsets(current_primes + [p], new_product, p) p += 1 generate_subsets([], 1, 0) return total # Example usage: N = int(input()) print(count_totient_bound(N))