読者です 読者をやめる 読者になる 読者になる

Qualification Round 1 問題B 日本語訳

GoogleCodeJam

問題B
http://code.google.com/codejam/contest/dashboard?c=433101#s=p1

我々の惑星「ジャムコードIX」では、大きな事件が3回起きた。
26000スラーボ秒前,11000スラーボ秒前,6000スラーボ秒前のことである。
今から4000スラーボ秒の後、それぞれの事件発生からの経過スラーボ秒が
ちょうど5000の倍数となる。これは経過スラーボ秒数を
割ることのできる数として最大であり、その時、世の終末が訪れる。

幸いなことに、あなたは「ジャムコードX」の住人だ!
「ジャムコードIX」には今年終末が訪れた。
そして「ジャムコードX」にも不安になるような予言が伝えられている。
「審判の時を経て、N回の大きな事件の記念となる日に
  世の終末は訪れるだろう。64bitは救いとはならない。これは警告だ。」

「ジャムコードX」の住人たちはこの予言をとても不安に思っている。
大きな事件は既に全て起こっており、経過スラーボ秒も計測されている。
しかし、「記念となる日」がいつなのかは誰も知らない。
「ジャムコードIX」の科学者の日記の研究を経て、
科学者たちはある説に辿りついた。

審判の時とは今、あなたが問題を解いている瞬間だ。
今からy≧0スラーボ秒の後、それぞれの事件からの
経過スラーボ秒がある最大数Tで割り切れる時が訪れる。
この最大数Tを与える最小のyを見つけることができれば、
世の終末が訪れる記念日を導くことができる。

例えば「ジャムコードIX」では、審判の時の
26000スラーボ秒前,11000スラーボ秒前,6000スラーボ秒前の
3回事件が起きた。4000スラーボ秒後、それぞれの事件発生からの
経過スラーボ秒がちょうど5000の倍数となり、終末が訪れた。
(訳者注: 30000と15000と10000の最大公約数が5000ですね。)

あなたの役目は終末までの時を計算することだ。
しかし予言を忘れないこと:
「ジャムコードX」の住人たちが二年間問題に取り組んでいて
64bit整数で事足りていたとしても、
今または将来も事足りるとは限らない。


■ 入力

1行目にテストケースの数Cが記され、その後C行が続きます。
それぞれNから始まり、スペースで区切られたN個の整数として
i番目の事件が起きてからの経過スラーボ数tiが続きます。

■ 出力

全てのテストケースにおいて、 "Case #x: y" という出力をして下さい。
ただし x は 1 から始まるテストケースIDで、
y は ti + y が最大約数 T で割り切れるような最小の数です。

■ 制限

1 ≦ C ≦ 100
ti ≠ tj となる i, j が少なくとも1組以上存在する。

■ Small dataset

2 ≦ N ≦ 3
1 ≦ ti ≦ 100,000,000

■ Large dataset

2 ≦ N ≦ 1,000
1 ≦ ti ≦ 10の50乗

■ エピローグ

ジャムコード系の人々にとって幸いなことに、
「世の終末」は「大パーティ」の誤訳であったことが判明した。
「ジャムコードIX」の住民たちは皆パーティに夢中で、
この情報を伝えることを忘れてしまっていたようだ。

入力例:

3
3 26000000 11000000 6000000
3 1 10 11
2 800000000000000000001 900000000000000000001

出力例:

Case #1: 4000000
Case #2: 0
Case #3: 99999999999999999999