CodeForces 687B Remainders Game

本文主要是介绍CodeForces 687B Remainders Game，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出n个数和一个k值，对于任意的x能不能在知道x mod Ci的前提下得到x mod k的值

对于任意的x可以通过x对ci取余得到一组数字，这组数组一共可以表示m个不同状态，m是所有n个Ci的最小公倍数，而当m是k的倍数的时候，每一个状态都会对应到一组数字，这组数字对k的余数都相等，所以问题就转化成了对n个数字求最小公倍数然后对k取余。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
int c[1000000], n, k;
ll gcd(ll a, ll b) {if(b)return gcd(b, a % b);return a;
}
int judge() {ll s = c[0] % k;for(int i = 1; i < n; i++) {s = s / gcd(s, c[i]) * c[i];s %= k;}if(!s)return 1;return 0;
}
int main() {while(~scanf("%d%d", &n, &k)) {for(int i = 0; i < n; i++) {scanf("%d", &c[i]);}if(judge())printf("Yes\n");else printf("No\n");}return 0;
}

这篇关于CodeForces 687B Remainders Game的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---