2021.07.20 CF1477A Nezzar and Board（最大公因数，未证）
CF1477A Nezzar and Board - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
重点：
1.最大公因数
题意：
黑板上有n个数ai，每次你可以选择其中两个数x，y，将2x-y写在黑板上，请问最后能不能得到k。
分析：
还不会，学会了再证。——2021.07.20
代码如下：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
#define int long long
int n,t,k,a[200010], gcdi;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
int gcd(int x,int y){
return !y?x:gcd(y,x%y);
}
signed main(){
//freopen("1.txt","r",stdin);
//freopen("1.out.txt","w",stdout);
t=read();
while(t--){
n=read();k=read();
for(int i=1;i<=n;i++)a[i]=read();
int ls=a[1];
k-=ls;
for(int i=1;i<=n;i++)a[i]-=ls;
gcdi=abs(a[2]);
for(int i=3;i<=n;i++)gcdi=gcd(gcdi,abs(a[i]));
if(k%gcdi)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
![2021-08-02：按公因数计算最大组件大小。给定一个由不同正整数的组成的非空数组 A，考虑下面的图：有 A.length 个节点，按从 A[0] 到 A[A.length - 1] 标记；只有当](https://www.kunjuke.com/file/css/thumb/7.jpg/280-180.jpg)
