結果

問題 No.8056 量子コンピュータで素因数分解 Easy
ユーザー 👑 MizarMizar
提出日時 2022-09-07 20:04:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 191 ms / 2,000 ms
コード長 573 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 73,112 KB
平均クエリ数 2.19
最終ジャッジ日時 2024-12-31 20:13:32
合計ジャッジ時間 5,038 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
import random
n = int(input())
while True:
    a = random.randrange(2, n - 1)
    gcda = math.gcd(n, a)
    if gcda > 1 and gcda < n:
        print("!", gcda, n // gcda)
        break
    print("?", a)
    b = int(input())
    if b % 2 == 1:
        continue
    b2 = b // 2
    powb2 = pow(a, b2, n)
    p = (powb2 + n - 1) % n
    gcdp = math.gcd(n, p)
    if p != 0 and gcdp > 1:
        print("!", gcdp, n // gcdp)
        break
    q = (powb2 + 1) % n
    gcdq = math.gcd(n, q)
    if q != 0 and gcdq > 1:
        print("!", gcdq, n // gcdq)
        break
0