結果

問題 No.8056 量子コンピュータで素因数分解 Easy
ユーザー Mizar
提出日時 2022-09-07 20:04:34
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 108 ms / 2,000 ms
+ 1µs
コード長 573 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 62 ms
コンパイル使用メモリ 81,268 KB
実行使用メモリ 58,820 KB
平均クエリ数 2.19
最終ジャッジ日時 2026-10-10 00:55:10
合計ジャッジ時間 3,453 ms
ジャッジサーバーID
(参考情報)
judge5_1 / judge3_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

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