結果

問題 No.551 夏休みの思い出（２）
ユーザー yuppe19 😺
提出日時 2020-08-23 13:58:24
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 406 ms / 4,000 ms
コード長 1,596 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-10-15 18:11:38
合計ジャッジ時間 11,599 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
# †
import random

def mod_inv(a, m):
    b, s, t = m, 1, 0
    while b:
        q = a // b
        a %= b
        a, b = b, a
        s -= t * q
        s, t = t, s
    if a != 1:
        return None
    return s + m if s < 0 else s


# ヤコビ記号 (a/n)
def jacobi(a, n):
    assert 0 < n and n & 1
    a %= n
    t = 1
    while a != 0:
        while a & 1 == 0:
            a >>= 1
            if n & 7 in (3, 5):
                t = -t
        a, n = n, a
        if a & 3 == 3 and n & 3 == 3:
            t = -t
        a %= n
    return t * (n == 1)


def mod_sqrt(n, p):
    if jacobi(n, p) == -1:
        return -1

    def mul(a, b, c, d, sq):
        x0 = (a*c + sq*b*d) % p
        x1 = (a*d + b*c) % p
        return x0, x1

    a = 1
    while jacobi(a*a - n, p) == 1:
        a = random.randint(1, p-1)
    m = (p+1) // 2
    sq = a*a - n
    r0, r1, x0, x1 = 1, 0, a, 1
    while m:
        if m & 1:
            r0, r1 = mul(r0, r1, x0, x1, sq)
        x0, x1 = mul(x0, x1, x0, x1, sq)
        m >>= 1
    return r0





###
if __name__ == '__main__':
    P, _ = map(int, input().split())
    Q = int(input())

    def f(a, b, c):
        D = (b*b - 4*a*c) % P
        inv2a = mod_inv(2*a, P)
        if D == 0:
            return -b * inv2a % P
        sq = mod_sqrt(D, P)
        if sq == -1:
            return -1
        x0 = (-b + sq) * inv2a % P
        x1 = (-b - sq) * inv2a % P
        return ' '.join(map(str, sorted([x0, x1])))

    for _ in range(Q):
        a, b, c = map(int, input().split())
        res = f(a, b, c)
        print(res)
0