結果

問題 No.185 和風
ユーザー itokoi4
提出日時 2025-06-22 13:28:36
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,357 bytes
コンパイル時間 173 ms
コンパイル使用メモリ 82,300 KB
実行使用メモリ 67,520 KB
最終ジャッジ日時 2025-06-22 13:28:38
合計ジャッジ時間 1,183 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

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


# yukikoder No.186 中華風(Easy)
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
    if ans:
        return ans
    else:
        return M
print(lagrange(a,m))
0