結果

問題 No.187 中華風 (Hard)
ユーザー koyumeishikoyumeishi
提出日時 2015-04-20 03:12:01
言語 Ruby
(3.3.0)
結果
WA  
実行時間 -
コード長 1,382 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 12,416 KB
最終ジャッジ日時 2024-07-04 16:45:55
合計ジャッジ時間 40,022 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,752 ms
12,288 KB
testcase_01 AC 1,768 ms
12,416 KB
testcase_02 AC 1,795 ms
12,416 KB
testcase_03 AC 1,762 ms
12,416 KB
testcase_04 AC 2,449 ms
12,160 KB
testcase_05 AC 2,494 ms
12,288 KB
testcase_06 AC 2,465 ms
12,288 KB
testcase_07 AC 2,469 ms
12,288 KB
testcase_08 AC 1,531 ms
12,416 KB
testcase_09 AC 1,523 ms
12,416 KB
testcase_10 AC 1,506 ms
12,288 KB
testcase_11 AC 2,478 ms
12,288 KB
testcase_12 AC 2,436 ms
12,416 KB
testcase_13 AC 558 ms
12,288 KB
testcase_14 AC 581 ms
12,288 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 88 ms
12,160 KB
testcase_18 AC 1,307 ms
12,160 KB
testcase_19 AC 84 ms
12,288 KB
testcase_20 AC 1,896 ms
12,288 KB
testcase_21 AC 82 ms
12,288 KB
testcase_22 AC 2,494 ms
12,416 KB
testcase_23 WA -
testcase_24 AC 82 ms
12,160 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:31: warning: assigned but unused variable - d
Main.rb:31: warning: assigned but unused variable - y
Syntax OK

ソースコード

diff # 

def gcd(a,b)
	if(b == 0) then
		return a
	end
	return gcd(b, a%b)
end

def lcm(a,b)
	if a<b then
		a,b = b,a
	end
	if(b==1) then
		return a
	end
	return a*(b/gcd(a,b))
end

def extgcd(a,b,x,y)
	d = a
	if(b!=0) then
		d,y,x = extgcd(b, a%b, y,x)
		y -= (a/b) * x
	else
		x = 1
		y = 0
	end
	return d,x,y
end

def mod_inv(a,m)
	d,x,y = extgcd(a,m,-1,-1)
	return (m+x%m)%m
end

#start = Time.now()

N = gets.to_i

x = Array.new(N)
y = Array.new(N)

for i in 0...N do
	x[i],y[i] = gets.split.map{|v| v.to_i}
end


#STDERR.puts Time.now - start

MOD = 10**9 + 7

valid = true

for i in 0...N do
	for j in i+1...N do
		if i!=j then
			g = gcd(y[i], y[j])

			if(x[i]%g != x[j]%g) then
				valid = false
			end

			if g != 1 then
				y[i] /= g
				y[j] /= g
				g_ = gcd(y[i], g)
				while g_ != 1 do
					y[i] *= g_
					g /= g_
					g_ = gcd(y[i], g)
				end
				y[j] *= g
				x[i] %= y[i]
				x[j] %= y[j]
			end
		end
	end
end

ans = 0


#STDERR.puts Time.now - start

for i in 0...N do
	for j in 0...i do
		x[i] = mod_inv(y[j], y[i]) * (x[i] - x[j])
		x[i] = (x[i] + y[i]) % y[i] 
	end
end

#STDERR.puts Time.now - start

tmp = 1
for i in 0...N do
	ans = (ans + x[i] * tmp) %MOD
	tmp = (tmp * y[i]) %MOD
end

if ans == 0 then
	lcm_ = 1
	for i in 0...N do
		lcm_ = lcm(lcm_, y[i]) %MOD
	end
	ans = lcm_
end

if valid == false then
	ans = -1
end

puts ans

#STDERR.puts Time.now - start
0