結果

問題 No.187 中華風 (Hard)
ユーザー itokoi4
提出日時 2025-06-22 15:06:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 690 ms / 3,000 ms
コード長 1,053 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 82,508 KB
実行使用メモリ 83,148 KB
最終ジャッジ日時 2025-06-22 15:06:14
合計ジャッジ時間 12,970 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
n=int(input())
xy=[list(map(int,input().split())) for i in range(n)]
MOD=10**9+7
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
    if ans:
        return ans
    else:
        return M
print(lagrange(a,m)%MOD)
0