結果

問題 No.187 中華風 (Hard)
ユーザー kmjp
提出日時 2015-04-19 23:56:17
言語 PyPy2
(7.1.1)
結果
AC  
実行時間 532 ms
コード長 629 Byte
コンパイル時間 748 ms
使用メモリ 87,248 KB
最終ジャッジ日時 2020-01-21 08:13:19

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0.in AC 124 ms
85,408 KB
1.in AC 112 ms
85,112 KB
2.in AC 304 ms
86,536 KB
3.in AC 300 ms
86,372 KB
4.in AC 500 ms
86,696 KB
5.in AC 492 ms
86,236 KB
6.in AC 496 ms
85,924 KB
7.in AC 496 ms
87,248 KB
8.in AC 500 ms
86,468 KB
9.in AC 520 ms
86,008 KB
A.in AC 492 ms
86,136 KB
B.in AC 476 ms
86,040 KB
C.in AC 488 ms
85,932 KB
D.in AC 140 ms
85,308 KB
E.in AC 116 ms
84,892 KB
F.in AC 176 ms
85,760 KB
G.in AC 196 ms
85,764 KB
H.in AC 96 ms
83,572 KB
I.in AC 112 ms
84,592 KB
J.in AC 104 ms
83,680 KB
K.in AC 392 ms
85,764 KB
L.in AC 116 ms
83,192 KB
M.in AC 532 ms
86,848 KB
N.in AC 108 ms
83,576 KB
system_test1.txt AC 100 ms
83,636 KB
テストケース一括ダウンロード

ソースコード

diff #
import sys
import math

def ext_gcd(p,q):
	if q==0:
		return (p,1,0)
	g,y,x = ext_gcd(q,p%q);
	y -= p/q*x
	return (g,x,y)

def cmt(a1,mo1,a2,mo2):
	g,x,y=ext_gcd(mo1,mo2)
	a1=(a1%mo1+mo1)%mo1
	a2=(a2%mo2+mo2)%mo2
	if a1%g != a2%g:
		return (-1,0)
	lcm=mo1*(mo2/g)
	if lcm<mo1:
		return (-2,0)
	v=a1+((a2-a1)%lcm+lcm)*x%lcm*(mo1/g)
	return (((v%lcm)+lcm) % lcm,lcm)

N=input()
P=[]
for i in range(N):
	P.append(map(int,raw_input().strip().split(" ")))

T=[P[0][0],P[0][1]]
for i in range(1,N):
	T2=cmt(T[0],T[1],P[i][0],P[i][1])
	if T2[0]<0:
		print -1
		sys.exit()
	T=[T2[0],T2[1]]

if T[0]==0:
	T[0]=T[1]

print T[0]%1000000007
0