#539068 (Python3) No.551 夏休みの思い出（２）

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#!/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)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX