結果
問題 |
No.186 中華風 (Easy)
|
ユーザー |
|
提出日時 | 2025-06-22 13:15:06 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 979 bytes |
コンパイル時間 | 345 ms |
コンパイル使用メモリ | 82,656 KB |
実行使用メモリ | 62,292 KB |
最終ジャッジ日時 | 2025-06-22 13:15:09 |
合計ジャッジ時間 | 2,337 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 WA * 2 |
ソースコード
from collections import defaultdict xy=[list(map(int,input().split())) for i in range(3)] cnt=defaultdict(list) for x,y in xy: for i in range(2,int(y**0.5)+1): c=0 while y%i==0: c+=1 y//=i if c: cnt[i].append((c,x%(i**c))) if y!=1: cnt[y].append((1,x%y)) a=[];m=[] for i in cnt: cnt[i].sort() if len(cnt[i])==1: a.append(cnt[i][0][1]) m.append(i**cnt[i][0][0]) else: for j in range(1,len(cnt[i])): c,aa=cnt[i][j] if aa%(i**cnt[i][0][0])!=cnt[i][0][1]: print(-1) exit() a.append(cnt[i][-1][1]) m.append(i**cnt[i][-1][0]) def lagrange(a,m): n=len(a) M=1 for i in range(n): M*=m[i] b=[] for i in range(n): Mi=M//m[i] b.append(Mi*pow(Mi,-1,m[i])) ans=0 for i in range(n): ans+=a[i]*b[i]%M ans%=M return ans print(lagrange(a,m))