結果

問題 No.3493 等比数列の和の素因数
コンテスト
ユーザー detteiuu
提出日時 2026-04-03 22:51:48
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 635 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 277 ms
コンパイル使用メモリ 85,004 KB
実行使用メモリ 81,776 KB
最終ジャッジ日時 2026-04-03 22:52:53
合計ジャッジ時間 29,392 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from random import randrange
from time import time

def inverse(n, d):
    return n * pow(d, -1, MOD) % MOD

def geometric_progression(a, r, n):
    # a = 初項 r = 公比 n = 項数
    return a*((pow(r, n, MOD)-1)%MOD)%MOD*inverse(1, r-1)%MOD

N, MOD = map(int, input().split())

if N == 0:
    exit(print("No"))

if MOD == 2:
    exit(print("Yes" if N%2 == 1 else "No"))

if (N+1)%MOD == 0 or geometric_progression(1, MOD-1, N+1) == 0:
    exit(print("Yes"))

start = time()
while time()-start <= 1.95:
    n = randrange(2, MOD)
    if geometric_progression(1, n, N+1) == 0:
        print("Yes")
        break
else:
    print("No")
0