結果
問題 |
No.1322 Totient Bound
|
ユーザー |
![]() |
提出日時 | 2025-06-12 21:16:40 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,320 bytes |
コンパイル時間 | 218 ms |
コンパイル使用メモリ | 82,444 KB |
実行使用メモリ | 148,224 KB |
最終ジャッジ日時 | 2025-06-12 21:17:28 |
合計ジャッジ時間 | 9,917 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 RE * 5 TLE * 1 -- * 20 |
ソースコード
import sys import math def main(): N = int(sys.stdin.readline()) if N == 0: print(0) return # We'll use a sieve to find primes up to N+2, but for large N, this is not feasible. # Instead, we'll find primes on the fly during the recursive process. # However, for the purpose of this solution, we'll assume a list of primes is available. # But in practice, generating primes on the fly is computationally expensive. # Therefore, we'll implement a helper function to generate primes up to sqrt(N) + 1. def is_prime(n): if n < 2: return False for p in range(2, int(math.sqrt(n)) + 1): if n % p == 0: return False return True primes = [] p = 2 while p <= N + 2: if is_prime(p): primes.append(p) p += 1 count = 0 def dfs(index, current_phi, current_x): nonlocal count if index >= len(primes): return p = primes[index] max_k = 0 while True: k = max_k + 1 new_phi_p = p**(k-1) * (p - 1) if new_phi_p > N: break max_k = k # Now try each k from 1 to max_k for k in range(1, max_k + 1): new_phi_p = p**(k-1) * (p - 1) if current_phi * new_phi_p > N: break new_phi = current_phi * new_phi_p new_x = current_x * (p ** k) # Count this new_x count += 1 # Proceed to next primes dfs(index + 1, new_phi, new_x) # Also consider not taking this prime at all dfs(index + 1, current_phi, current_x) # Start the DFS with the first prime, current_phi=1, current_x=1 # But wait, x=1 is already counted, but in our initial call, current_x is 1, which is x=1, which is counted. # So we need to adjust the initial call to count x=1. # Alternatively, we can start with current_phi=1 and current_x=1, and then in the loop, the first prime's exponents will generate x=2,3, etc. # Initialize the count with x=1 # Because when no primes are chosen, current_x=1, current_phi=1, which is counted count = 1 # x=1 is counted dfs(0, 1, 1) print(count) if __name__ == "__main__": main()