結果

問題 No.1312 Snake Eyes
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:09:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 96 ms / 2,000 ms
コード長 1,570 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 82,416 KB
実行使用メモリ 62,708 KB
最終ジャッジ日時 2025-03-20 21:10:10
合計ジャッジ時間 6,997 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    N = int(input().strip())
    min_p = N + 1  # Initialize with k=1 case

    # Function to get all divisors of N
    def get_divisors(n):
        divisors = set()
        for i in range(1, int(math.isqrt(n)) + 1):
            if n % i == 0:
                divisors.add(i)
                divisors.add(n // i)
        return sorted(divisors)

    # Handle k=2 case
    divisors = get_divisors(N)
    for m in divisors:
        if m < 2:
            continue
        p_candidate = m - 1
        if p_candidate < 2:
            continue
        if N % m != 0:
            continue
        d = N // m
        if d < p_candidate and d >= 1:
            if p_candidate < min_p:
                min_p = p_candidate

    # Handle k >=3 cases
    max_k = 60  # Sufficiently large to cover possible k values
    for k in range(3, max_k + 1):
        p = 2
        while True:
            # Compute m = (p^k -1) // (p-1)
            try:
                numerator = pow(p, k) - 1
                denominator = p - 1
                if denominator == 0:
                    break  # Avoid division by zero (p=1 is not possible here)
                m = numerator // denominator
            except:
                break  # In case of overflow, though in Python it's unlikely
            if m > N:
                break
            if N % m == 0:
                d = N // m
                if d < p and d >= 1:
                    if p < min_p:
                        min_p = p
            p += 1

    print(min_p)

if __name__ == "__main__":
    main()
0