题解 CF299A 【Ksusha and Array】

第一道会题题解，也是通过的第一道灰题 题目大意：找出序列a中被所有数整除的数 思路非常简单，即求出所有数的最大公约数 ``` int long long GCD(int long long x,int long long y){ if(y==0)return x; return GCD(y,x%y); } //主函数 gcd[1]=a[1]; for(int i=2;i<=n;i++)gcd=GCD(gcd,a[i]); //这里不建议使用algorithm库里的__gcd函数，long long容易出现未知错误 ``` 看上面的大佬求出最大公约数还穷举了gcd的因子，其实多此一举 只需要判断gcd是否在序列a中就可以了 这里给出证明（口胡）： 这里求出的gcd显然会小于等于数列a中最小的数 假设gcd存在一个因子满足条件，即这个因子出现在了数列a中，那么求得的gcd应该小于等于这个因子，矛盾 得证 csp rp--！！！~~反奶一口~~ AC code ``` #include<iostream> using namespace std; int n,a[1000005],gcd; int GCD(int x,int y){ if(y==0)return x; return GCD(y,x%y); } int main() { scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); gcd=a[1]; for(int i=2;i<=n;i++) gcd=GCD(gcd,a[i]); for(int i=1;i<=n;i++) { if(a[i]==gcd) { printf("%d",&a[i]); return 0; } } printf("-1"); return 0; } ```