結果

問題 No.551 夏休みの思い出（２）
ユーザー yuppe19 😺yuppe19 😺
提出日時 2020-08-23 13:58:24
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 366 ms / 4,000 ms
コード長 1,596 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-04-23 17:37:14
合計ジャッジ時間 9,850 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
11,392 KB
testcase_01 AC 29 ms
11,392 KB
testcase_02 AC 31 ms
11,264 KB
testcase_03 AC 40 ms
11,264 KB
testcase_04 AC 49 ms
11,392 KB
testcase_05 AC 78 ms
11,392 KB
testcase_06 AC 99 ms
11,392 KB
testcase_07 AC 30 ms
11,392 KB
testcase_08 AC 29 ms
11,264 KB
testcase_09 AC 29 ms
11,392 KB
testcase_10 AC 30 ms
11,264 KB
testcase_11 AC 33 ms
11,392 KB
testcase_12 AC 31 ms
11,392 KB
testcase_13 AC 30 ms
11,392 KB
testcase_14 AC 29 ms
11,392 KB
testcase_15 AC 30 ms
11,264 KB
testcase_16 AC 29 ms
11,264 KB
testcase_17 AC 30 ms
11,264 KB
testcase_18 AC 30 ms
11,392 KB
testcase_19 AC 32 ms
11,392 KB
testcase_20 AC 33 ms
11,392 KB
testcase_21 AC 34 ms
11,264 KB
testcase_22 AC 32 ms
11,264 KB
testcase_23 AC 32 ms
11,264 KB
testcase_24 AC 33 ms
11,264 KB
testcase_25 AC 32 ms
11,264 KB
testcase_26 AC 33 ms
11,264 KB
testcase_27 AC 346 ms
11,264 KB
testcase_28 AC 324 ms
11,392 KB
testcase_29 AC 305 ms
11,264 KB
testcase_30 AC 327 ms
11,392 KB
testcase_31 AC 300 ms
11,392 KB
testcase_32 AC 322 ms
11,392 KB
testcase_33 AC 331 ms
11,264 KB
testcase_34 AC 314 ms
11,264 KB
testcase_35 AC 304 ms
11,264 KB
testcase_36 AC 319 ms
11,264 KB
testcase_37 AC 366 ms
11,392 KB
testcase_38 AC 361 ms
11,264 KB
testcase_39 AC 344 ms
11,392 KB
testcase_40 AC 352 ms
11,264 KB
testcase_41 AC 338 ms
11,264 KB
testcase_42 AC 360 ms
11,264 KB
testcase_43 AC 354 ms
11,392 KB
testcase_44 AC 356 ms
11,392 KB
testcase_45 AC 328 ms
11,392 KB
testcase_46 AC 357 ms
11,264 KB
testcase_47 AC 30 ms
11,264 KB
testcase_48 AC 29 ms
11,264 KB
権限があれば一括ダウンロードができます

ソースコード

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