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

Summary:

Given integer n, k < 1M, and n numbers c[1], ..., c[n] < 1M, decide whether we can always guess for all unknown integer x, what x mod k is if x mod c[i] is known for all i.

Solution:

This problem has a cool solution. For a given c[i] and k, we cannot always decide what x is if there exist x and y such that x = y mod c[i] but x != y mod k. This is equivalent to x-y = 0 mod c[i] and x-y != 0 mod k, which means c[i] divides x-y, but k does not divides x-y. This means x-y = LM where L is lcm(c[1], c[2], ..., c[n]) and M is the rest of the factor. Since k does not divide x-y, then k does not divides L. Hence we conclude that if we cannot always decide what x is, then k does not divide L.

Now let's go the other direction. If k does not divide L, then we can choose x = 2L and y = L, such that x-y = L which is divisible by all c[i] but not k. This is equivalent to saying x = y mod c[i] but x != y mod k, meaning we cannot always decide what x is for the given set of c[i] and k.

Hence the problem reduces to checking if k divides L = lcm(c[1], c[2], ..., c[n]). Focus on p, a prime factor of k. Suppose t is the max integer such that p^t | k. What we need to check is if L has at least t power of p. Notice that lcm(a, b) maximises the power of p. On the other hand, gcd(a, b) minimises the power of p. For example a = 2^3 x 3^4 and b = 2^5 x 3^1 then lcm(a, b) = 2^max(3, 5) x 3^max(4,1). On the other hand gcd(a, b) = 2^min(3,5) x 3^min(4,1).

With this we have the following implementation:

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int Gcd(int64_t a, int64_t b) { if (a<b) swap(a,b); if (b == 0) return a; return Gcd(b, a%b); } int64_t Lcm(int a, int b) { return 1LL * a * b / Gcd(a, b); } int main(){ int n, k; scanf("%d%d",&n,&k); int c; int trail = 1; for(int i=0;i<n;++i){ scanf("%d",&c); trail = Gcd(k, Lcm(trail, c)); } if (trail == k) printf("Yes\n"); else printf("No\n"); return 0; }

On each iteration, 'trail' contains the maximum power of prime factor p of k over c[1], c[2], ..., c[i] (bounded at the actual power of p in k) for each p. Hence Gcd(k, ...) serves the purpose of truncating all prime factors in c[i] that does not matter, and limiting the power of each prime factor of k to not exceed k.