Codeforces Round #360 (Div. 1) - B. Remainders Game

Problem Statement:
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.