結果

問題 No.551 夏休みの思い出（２）
ユーザー lam6er
提出日時 2025-03-20 18:52:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 261 ms / 4,000 ms
コード長 2,364 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 81,600 KB
最終ジャッジ日時 2025-03-20 18:53:46
合計ジャッジ時間 7,458 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import random

def cipolla(n, p):
    if n == 0:
        return (0, 0)
    legendre = pow(n, (p - 1) // 2, p)
    if legendre not in (0, 1):
        return ()
    if legendre == 0:
        return (0, 0)
    
    while True:
        a = random.randint(0, p - 1)
        w = (a * a - n) % p
        if pow(w, (p - 1) // 2, p) == p - 1:
            break

    def multiply(x1, y1, x2, y2):
        return ((x1 * x2 + y1 * y2 * w) % p, (x1 * y2 + x2 * y1) % p)
    
    m = (p + 1) // 2
    res_x, res_y = 1, 0
    curr_x, curr_y = a, 1
    
    while m > 0:
        if m % 2 == 1:
            res_x, res_y = multiply(res_x, res_y, curr_x, curr_y)
        curr_x, curr_y = multiply(curr_x, curr_y, curr_x, curr_y)
        m = m // 2
    assert res_y == 0
    return (res_x, (p - res_x) % p)

def solve_equation(P, inv2, a_i, B_i, C_i):
    a_inv = pow(a_i, P - 2, P)
    B_prime = (B_i * a_inv) % P
    C_prime = (C_i * a_inv) % P
    D = (B_prime * B_prime - 4 * C_prime) % P
    
    solutions = []
    
    if D == 0:
        x = (-B_prime * inv2) % P
        solutions.append(x)
    else:
        legendre = pow(D, (P - 1) // 2, P)
        if legendre == P - 1:
            pass
        else:
            if legendre == 1:
                if P % 4 == 3:
                    root = pow(D, (P + 1) // 4, P)
                    roots = [root, (P - root) % P]
                else:
                    roots = cipolla(D, P)
                r1, r2 = roots
                x1 = ((-B_prime + r1) * inv2) % P
                x2 = ((-B_prime + r2) * inv2) % P
                solutions.extend([x1, x2])
                unique_solutions = list(set(solutions))
                unique_solutions.sort()
                solutions = unique_solutions
    
    if not solutions:
        return "-1"
    else:
        solutions = sorted(solutions)
        return ' '.join(map(str, solutions))

def main():
    input = sys.stdin.read().split()
    ptr = 0
    P = int(input[ptr])
    ptr +=1
    R = int(input[ptr])
    ptr +=1
    Q = int(input[ptr])
    ptr +=1
    
    inv2 = pow(2, P - 2, P)
    
    for _ in range(Q):
        a_i = int(input[ptr])
        ptr +=1
        B_i = int(input[ptr])
        ptr +=1
        C_i = int(input[ptr])
        ptr +=1
        
        print(solve_equation(P, inv2, a_i, B_i, C_i))
        
if __name__ == "__main__":
    main()
0