CodeForces - 1477A - Nezzar and Board(数论)

简介: 笔记

Nezzar and Board


题意

对 一个大小为n 的整数集合 进行操作 每次可以选取两个数x,y 得到 2x−y 加入这个集合

问 经过无限次这样的操作之后 能否得到k


思路

1.png

代码

#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;
}
目录
相关文章
|
6天前
PTA-求100以内的素数
求100以内的素数
19 0
|
6天前
PTA-求指定范围内的素数
求指定范围内的素数
26 0
|
数据安全/隐私保护
Codeforces 417D.Cunning Gena (状压DP)
Codeforces 417D.Cunning Gena (状压DP)
66 0
|
人工智能 vr&ar Perl
codeforces1509 C. The Sports Festival (区间DP)
codeforces1509 C. The Sports Festival (区间DP)
88 0
|
人工智能
codeforces455——A. Boredom(线性DP)
codeforces455——A. Boredom(线性DP)
102 0
codeforces455——A. Boredom(线性DP)
[Codeforces] 1557 C Moamen and XOR(组合数学)
题意: 用 < 2k的数填充到长度为n的数组中,要使得数组中所有数& >= ^,问方案数 显然,当k == 1的时候,答案为1,只有当所有的数全为1的情况才可以满足题意 对于其他的情况{ 用小于2k的数进行填充,那么说明填充的数字的二进制位数最多可以有k kk位, 从数的个数的角度来说,奇数个1^ 之后的结果是1,偶数个1^ 之后的结果是0,而对于0来讲,不管多少个0,^起来结果都是0 只要有一个0,那么说这一位上&之后就是0,而为了让^为0,那么只能够选择偶数个1 如果某一位上&为1,那么^为1的情况需要讨论n的奇偶性
101 0