結果

問題 No.1322 Totient Bound
コンテスト
ユーザー gew1fw
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0