Remainders Game [Codeforces 360 : Div1 B, Div2 D]

問題

http://codeforces.com/problemset/problem/687/B

2人でするゲームです。
Aさんは2つの数(x, k)を決めて、xは隠し、kはBさんに伝える。
それとは別に、2人とも知っている数列 C = (c1, c2, ..., cn) を用意する。
そして、AさんはBさんに x mod c1, x mod c2, ..., x mod cn の値を伝える。
Bさんはこの情報を元に x mod k の値を推理できるか。
できれば「Yes」できなければ「No」

1 <= n, k <= 10^6
1 <= ci <= 10^6

思考の流れ

1. まずどんな時に推理できるか考えます
2. 実験しながらすごく考えます
3. 今回は考察ゲーなので、以下の2定理が導けないと厳しいです(凄い人はこれを一瞬で導けるの？なにか有名なものなの？)

• x mod kn が分かれば x mod n が分かる

つまり、x mod 6 が分かれば x mod 3 も分かる
これはまだ気づけそう

• x mod a と x mod b が分かれば x mod lcm(a,b) も分かる

これは微妙。x mod 2 と x mod 3 が分かれば x mod 6 も実は分かる

※lcmは最小公倍数のこと
（lcmは最大公約数gcdから求められ、gcdは高速に求めるメソッドがある。知らない人はググろう！）

4. c1～cnのlcmをとり、これがkの倍数であれば「Yes」
5. 普通にlcmをとるとオーバーフローを起こしてしまう
6. 「kの倍数である -> gcd(?,k)=kである」ことを利用
7. ciを処理する時に、lcmをとってgcdをとってとすれば、gcdをとった後はk以下の数になるためオーバーフローを防げる

解法

http://codeforces.com/contest/687/submission/18816535

int n, k;
//-----------------------------------------------------------------
typedef long long ll;
ll gcd(ll a, ll b) { return a ? gcd(b%a, a) : b; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
//-----------------------------------------------------------------
int main() {
	scanf("%d %d", &n, &k);

	ll s = 1;
	rep(i, 0, n) {
		int c; scanf("%d", &c);
		s = lcm(s, c);
		s = gcd(s, k);
	}

	if (s == k)
		printf("Yes\n");
	else
		printf("No\n");
}