結果
問題 |
No.1322 Totient Bound
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:14:42 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,394 bytes |
コンパイル時間 | 239 ms |
コンパイル使用メモリ | 82,136 KB |
実行使用メモリ | 116,412 KB |
最終ジャッジ日時 | 2025-06-12 21:16:21 |
合計ジャッジ時間 | 7,555 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 TLE * 1 -- * 25 |
ソースコード
import sys import math def main(): sys.setrecursionlimit(1 << 25) N = int(sys.stdin.readline().strip()) if N == 0: print(0) return # Function to generate primes up to n using sieve of Eratosthenes def sieve(n): sieve = [True] * (n + 1) sieve[0] = sieve[1] = False for i in range(2, int(math.sqrt(n)) + 1): if sieve[i]: sieve[i*i : n+1 : i] = [False]*len(sieve[i*i : n+1 : i]) primes = [i for i, is_prime in enumerate(sieve) if is_prime] return primes max_prime = N + 1 primes = sieve(max_prime) primes.sort() count = 0 # Recursive function to explore combinations of primes and exponents def dfs(index, current_phi): nonlocal count if current_phi > N: return count += 1 for i in range(index, len(primes)): p = primes[i] k = 1 while True: contribution = (p - 1) * (p ** (k - 1)) if contribution > N: break next_phi = current_phi * contribution if next_phi > N: # Prune the search break dfs(i + 1, next_phi) k += 1 # Start with current_phi = 1 (x = 1) dfs(0, 1) print(count) if __name__ == "__main__": main()