結果

問題 No.551 夏休みの思い出（２）
ユーザー NatsubiSoganNatsubiSogan
提出日時 2021-12-12 22:33:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 576 ms / 4,000 ms
コード長 1,375 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 83,304 KB
最終ジャッジ日時 2024-07-21 10:57:38
合計ジャッジ時間 15,851 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 68 ms
68,352 KB
testcase_01 AC 81 ms
69,504 KB
testcase_02 AC 101 ms
74,368 KB
testcase_03 AC 181 ms
78,976 KB
testcase_04 AC 218 ms
79,232 KB
testcase_05 AC 324 ms
80,352 KB
testcase_06 AC 420 ms
82,188 KB
testcase_07 AC 89 ms
71,552 KB
testcase_08 AC 93 ms
71,936 KB
testcase_09 AC 91 ms
71,936 KB
testcase_10 AC 91 ms
71,296 KB
testcase_11 AC 96 ms
71,936 KB
testcase_12 AC 86 ms
71,808 KB
testcase_13 AC 79 ms
71,040 KB
testcase_14 AC 78 ms
71,296 KB
testcase_15 AC 75 ms
70,656 KB
testcase_16 AC 76 ms
71,168 KB
testcase_17 AC 83 ms
73,856 KB
testcase_18 AC 99 ms
78,336 KB
testcase_19 AC 101 ms
78,208 KB
testcase_20 AC 97 ms
77,952 KB
testcase_21 AC 94 ms
78,208 KB
testcase_22 AC 95 ms
78,208 KB
testcase_23 AC 96 ms
78,336 KB
testcase_24 AC 79 ms
73,600 KB
testcase_25 AC 81 ms
73,344 KB
testcase_26 AC 94 ms
75,264 KB
testcase_27 AC 461 ms
81,732 KB
testcase_28 AC 467 ms
82,260 KB
testcase_29 AC 483 ms
82,788 KB
testcase_30 AC 461 ms
82,148 KB
testcase_31 AC 576 ms
83,152 KB
testcase_32 AC 475 ms
82,068 KB
testcase_33 AC 494 ms
83,304 KB
testcase_34 AC 477 ms
82,596 KB
testcase_35 AC 544 ms
82,276 KB
testcase_36 AC 483 ms
82,108 KB
testcase_37 AC 454 ms
81,700 KB
testcase_38 AC 489 ms
82,352 KB
testcase_39 AC 495 ms
83,088 KB
testcase_40 AC 424 ms
81,712 KB
testcase_41 AC 437 ms
82,212 KB
testcase_42 AC 515 ms
82,020 KB
testcase_43 AC 510 ms
83,120 KB
testcase_44 AC 481 ms
82,948 KB
testcase_45 AC 457 ms
82,824 KB
testcase_46 AC 485 ms
81,800 KB
testcase_47 AC 80 ms
68,096 KB
testcase_48 AC 79 ms
67,712 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import random
def mod_sqrt(a: int, p: int) -> int:
	if a == 0: return 0
	if p == 2: return 1
	k = (p - 1) // 2
	if pow(a, k, p) != 1: return -1
	while True:
		n = random.randint(2, p - 1)
		r = (n ** 2 - a) % p
		if r == 0: return n
		if pow(r, k, p) == p - 1: break
	k += 1
	w, x, y, z = n, 1, 1, 0
	while k:
		if k % 2:
			y, z = w * y + r * x * z, x * y + w * z
		w, x = w * w + r * x * x, 2 * w * x
		w %= p; x %= p; y %= p; z %= p
		k >>= 1
	return y
import typing
# 拡張Euclidの互除法
def extgcd(a: int, b: int, d: int = 0) -> typing.Tuple[int, int, int]:
	g = a
	if b == 0:
		x, y = 1, 0
	else:
		x, y, g = extgcd(b, a % b)
		x, y = y, x - a // b * y
	return x, y, g
 
# mod p における逆元
def invmod(a: int, p: int) -> int:
	x, y, g = extgcd(a, p)
	x %= p
	return x
p, r = map(int, input().split())
q = int(input())
for _ in range(q):
	a, b, c = map(int, input().split())
	n = ((b ** 2) * invmod(4 * a, p) % p - c) * invmod(a, p) % p
	m = mod_sqrt(n, p)
	ans = []
	if m == 0:
		tmp = (m - b * invmod(2 * a, p)) % p
		if (a * tmp ** 2 + b * tmp + c) % p == 0: ans.append(tmp)
	else:
		m2 = p - m
		x, y = (m - b * invmod(2 * a, p)) % p, (m2 - b * invmod(2 * a, p)) % p
		if x > y: x, y = y, x
		if (a * x ** 2 + b * x + c) % p == 0: ans.append(x)
		if (a * y ** 2 + b * y + c) % p == 0: ans.append(y)
	if len(ans) == 0: print(-1)
	else: print(*sorted(ans))
0