結果
問題 | No.551 夏休みの思い出(2) |
ユーザー | vwxyz |
提出日時 | 2021-08-01 20:29:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 424 ms / 4,000 ms |
コード長 | 2,933 bytes |
コンパイル時間 | 654 ms |
コンパイル使用メモリ | 87,036 KB |
実行使用メモリ | 99,076 KB |
最終ジャッジ日時 | 2023-10-14 19:02:12 |
合計ジャッジ時間 | 18,858 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 276 ms
92,980 KB |
testcase_01 | AC | 277 ms
92,804 KB |
testcase_02 | AC | 285 ms
94,980 KB |
testcase_03 | AC | 314 ms
96,740 KB |
testcase_04 | AC | 351 ms
97,248 KB |
testcase_05 | AC | 364 ms
97,340 KB |
testcase_06 | AC | 349 ms
97,640 KB |
testcase_07 | AC | 278 ms
92,700 KB |
testcase_08 | AC | 281 ms
92,716 KB |
testcase_09 | AC | 276 ms
92,876 KB |
testcase_10 | AC | 277 ms
93,104 KB |
testcase_11 | AC | 276 ms
92,872 KB |
testcase_12 | AC | 281 ms
92,836 KB |
testcase_13 | AC | 279 ms
92,960 KB |
testcase_14 | AC | 278 ms
92,808 KB |
testcase_15 | AC | 278 ms
92,992 KB |
testcase_16 | AC | 276 ms
92,824 KB |
testcase_17 | AC | 272 ms
93,036 KB |
testcase_18 | AC | 272 ms
93,248 KB |
testcase_19 | AC | 276 ms
92,704 KB |
testcase_20 | AC | 273 ms
93,024 KB |
testcase_21 | AC | 274 ms
92,852 KB |
testcase_22 | AC | 274 ms
92,624 KB |
testcase_23 | AC | 273 ms
93,060 KB |
testcase_24 | AC | 273 ms
92,720 KB |
testcase_25 | AC | 273 ms
93,072 KB |
testcase_26 | AC | 273 ms
92,708 KB |
testcase_27 | AC | 398 ms
97,812 KB |
testcase_28 | AC | 367 ms
97,924 KB |
testcase_29 | AC | 382 ms
98,348 KB |
testcase_30 | AC | 414 ms
98,988 KB |
testcase_31 | AC | 354 ms
97,652 KB |
testcase_32 | AC | 411 ms
99,076 KB |
testcase_33 | AC | 368 ms
98,368 KB |
testcase_34 | AC | 395 ms
97,456 KB |
testcase_35 | AC | 363 ms
97,456 KB |
testcase_36 | AC | 370 ms
98,128 KB |
testcase_37 | AC | 371 ms
97,576 KB |
testcase_38 | AC | 410 ms
97,696 KB |
testcase_39 | AC | 368 ms
98,264 KB |
testcase_40 | AC | 370 ms
98,028 KB |
testcase_41 | AC | 424 ms
97,396 KB |
testcase_42 | AC | 371 ms
98,000 KB |
testcase_43 | AC | 369 ms
97,464 KB |
testcase_44 | AC | 367 ms
97,800 KB |
testcase_45 | AC | 371 ms
98,424 KB |
testcase_46 | AC | 395 ms
97,776 KB |
testcase_47 | AC | 276 ms
92,952 KB |
testcase_48 | AC | 276 ms
92,724 KB |
ソースコード
import bisect import copy import decimal import fractions import heapq import itertools import math import random import sys from collections import Counter,deque,defaultdict from functools import lru_cache,reduce from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max def _heappush_max(heap,item): heap.append(item) heapq._siftdown_max(heap, 0, len(heap)-1) def _heappushpop_max(heap, item): if heap and item < heap[0]: item, heap[0] = heap[0], item heapq._siftup_max(heap, 0) return item from math import gcd as GCD, inf, modf read=sys.stdin.read readline=sys.stdin.readline readlines=sys.stdin.readlines def Extended_Euclid(n,m): stack=[] while m: stack.append((n,m)) n,m=m,n%m if n>=0: x,y=1,0 else: x,y=-1,0 for i in range(len(stack)-1,-1,-1): n,m=stack[i] x,y=y,x-(n//m)*y return x,y class MOD: def __init__(self,mod): self.mod=mod def Pow(self,a,n): a%=self.mod if n>=0: return pow(a,n,self.mod) else: assert math.gcd(a,self.mod)==1 x=Extended_Euclid(a,self.mod)[0] return pow(x,-n,self.mod) def Build_Fact(self,N): assert N>=0 self.factorial=[1] for i in range(1,N+1): self.factorial.append((self.factorial[-1]*i)%self.mod) self.factorial_inv=[None]*(N+1) self.factorial_inv[-1]=self.Pow(self.factorial[-1],-1) for i in range(N-1,-1,-1): self.factorial_inv[i]=(self.factorial_inv[i+1]*(i+1))%self.mod return self.factorial_inv def Fact(self,N): return self.factorial[N] def Fact_Inv(self,N): return self.factorial_inv[N] def Comb(self,N,K): if K<0 or K>N: return 0 s=self.factorial[N] s=(s*self.factorial_inv[K])%self.mod s=(s*self.factorial_inv[N-K])%self.mod return s def Tonelli_Shanks(N,p): if pow(N,p>>1,p)==p-1: retu=None elif p%4==3: retu=pow(N,(p+1)//4,p) else: for nonresidue in range(1,p): if pow(nonresidue,p>>1,p)==p-1: break pp=p-1 cnt=0 while pp%2==0: pp//=2 cnt+=1 s=pow(N,pp,p) retu=pow(N,(pp+1)//2,p) for i in range(cnt-2,-1,-1): if pow(s,1<<i,p)==p-1: s*=pow(nonresidue,p>>1+i,p) s%=p retu*=pow(nonresidue,p>>2+i,p) retu%=p return retu P,R=map(int,readline().split()) Q=int(readline()) MD=MOD(P) for _ in range(Q): A,B,C=map(int,readline().split()) D=(B**2-4*A*C)%P d=Tonelli_Shanks(D,P) ans_set=set() if d==None: ans_set.add(-1) else: rev=MD.Pow(2*A,-1) ans_set.add((-B+d)*rev%P) ans_set.add((-B-d)*rev%P) print(*sorted(list(ans_set)))