結果

問題 No.1322 Totient Bound
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:23:14
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,394 bytes
コンパイル時間 514 ms
コンパイル使用メモリ 82,228 KB
実行使用メモリ 116,576 KB
最終ジャッジ日時 2025-06-12 16:23:38
合計ジャッジ時間 7,791 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

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