题意
- 给出数列 \(S=\{a_i\}\) 和整数 \(k\),求是否能通过下面的操作使得 \(k\in S\)?
- 操作:选取 \(x,y\in S\),将 \(2x-y\) 加入 \(S\) 中。
分析
- 观察操作可以发现,\(2x-y\) 实际上就是数轴上 \(y\) 关于 \(x\) 的对称点,因此这个操作只与 \(x\) 和 \(y\) 在数轴上的相对位置有关,与具体位置(具体数值)无关。继续观察可以发现,如果 \(0\in S\),那么就会有几个很好的性质:
- 若 \(x\in S\),那么 \(n\cdot x\in S,n\in\mathbb{Z}\)。
- 若 \(x,y\in S\),那么 \(x+y\in S\)。
- 为了可以利用这两条性质,我们可以将 \(S\) 变化为 \(S'=\{a_i-a_1\}\),并把 \(k\) 减去 \(a_1\)(就相当于将数轴平移了)。此时 \(0\in S'\),因此在无限次进行操作之后,得到的就是 \(S'\) 的整线性组合 \(S''=\{x|x=m\cdot\gcd(a_2,a_3,\cdots,a_n),m\in\mathbb{Z}\}\),判断 \(k\in S''\) 即判断 \(\gcd(a_2,a_3,\cdots,a_n)\mid k\),直接求解即可。
AC 代码
#include <bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int n, k, a[N];
inline int read(int &x) {
char ch = x = 0;
int m = 1;
while (ch < '0' || ch > '9') {
ch = getchar();
if (ch == '-') m *= -1;
}
while (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + ch - 48;
ch = getchar();
}
x *= m;
return x;
}
int gcd(int x, int y) {
if (y == 0) return x;
return gcd(y, x % y);
}
signed main() {
int T;
read(T);
while (T--) {
read(n), read(k);
for (int i = 1; i <= n; i++) read(a[i]);
sort(a + 1, a + 1 + n);
for (int i = 2; i <= n; i++) a[i] -= a[1]; //平移数轴
k -= a[1];
if (k == 0) { //避免取余 k
printf("YES\n");
continue;
}
a[1] = 0;
int g = a[2];
for (int i = 3; i <= n; i++) g = gcd(g, a[i]); //求解 gcd
if (k % g) printf("NO\n");
else printf("YES\n");
}
return 0;
}
标签:Nezzar,ch,数轴,int,题解,CF1477A,while,操作
From: https://www.cnblogs.com/iloveoi/p/18037745