Nezzar and Board
题意
对 一个大小为n 的整数集合 进行操作 每次可以选取两个数x,y 得到 2x−y 加入这个集合
问 经过无限次这样的操作之后 能否得到k
思路
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 using namespace std; typedef long long LL; typedef pair<int, int>PII; inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } const int N = 200010; LL n, k; LL a[N]; void solve() { cin >> n >> k; LL res = 0; for (int i = 1; i <= n; ++i) { cin >> a[i]; //res = gcd(res, a[i] - a[i - 1]); } for (int i = 2; i <= n; ++i) res = gcd(res, a[i] - a[i - 1]); for (int i = 1; i <= n; ++i) { if ((k - a[i]) % res == 0) { puts("YES"); return; } } puts("NO"); } int main() { int t; cin >> t; while (t--) solve(); return 0; }
