Codeforces 687B Remainders Game

链接

传送门

题意

给出整数\(n,k(1 \leq n, k \leq 1000000)\)，接着给出\(n\)个整数\(c_i\)，在已知\(x \mod {c_i}\)的前提下，能否唯一的确定\(x \mod k\)。

思路

将\(k\)进行分解，对于每个质数，如果都存在\(c_i\)中的质数的幂比\(k\)中的大，则能唯一的确定\(x \mod k\)。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

LL gcd(LL a, LL b) {
  return b ? gcd(b, a % b) : a;
}

LL lcm(LL a, LL b) {
  return a / gcd(a, b) * b;
}

int main() {
  int n, k, c;
  LL cur = 1;
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &c);
    cur = lcm(cur, gcd(c, k));
  }
  puts(cur == k ? "Yes" : "No");
  return 0;
}