結果

問題 No.187 中華風 (Hard)
ユーザー kmjp
提出日時 2015-04-19 23:56:17
言語 PyPy2
(7.1.1)
結果
AC  
実行時間 511 ms
コード長 629 Byte
コンパイル時間 130 ms
使用メモリ 75,636 KB
最終ジャッジ日時 2019-09-14 03:15:29

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0.in AC 121 ms
72,704 KB
1.in AC 119 ms
72,608 KB
2.in AC 291 ms
74,488 KB
3.in AC 283 ms
74,208 KB
4.in AC 485 ms
74,712 KB
5.in AC 480 ms
74,700 KB
6.in AC 478 ms
73,812 KB
7.in AC 493 ms
75,636 KB
8.in AC 509 ms
73,932 KB
9.in AC 501 ms
73,788 KB
A.in AC 511 ms
73,732 KB
B.in AC 474 ms
74,172 KB
C.in AC 483 ms
74,228 KB
D.in AC 124 ms
73,532 KB
E.in AC 124 ms
73,028 KB
F.in AC 174 ms
73,576 KB
G.in AC 189 ms
74,440 KB
H.in AC 106 ms
72,348 KB
I.in AC 119 ms
73,272 KB
J.in AC 103 ms
72,160 KB
K.in AC 376 ms
73,764 KB
L.in AC 106 ms
71,628 KB
M.in AC 495 ms
74,700 KB
N.in AC 102 ms
72,028 KB
system_test1.txt AC 104 ms
71,568 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