题解 | 小红的gcd
小红的gcd
https://www.nowcoder.com/practice/5500a375098947c482b2c4787057cb13
观察样例大胆猜测：答案是
因为任意两个数的gcd一定有一个因子是总体的gcd，也就是这个数一定是总体的倍数，连续gcd后，最终的数必然都会变成全体的最大公约数，不可能比这个还小，因为gcd最小就能让一个数减少到全体的公约数，不会使得一个数比这个全体的公约数还要小，因此我们简单证明了这个答案是最小的，另外再证明这个答案一定取得到，只需要第一个与第二个操作，第二个与第三个操作，以此类推，第一个与第二个操作变成__gcd(a1,a2)，第二个与第三个操作变成__gcd( ___gcd(a1,a2),a3)，一趟下来与求gcd(a1,a2,a3,...,an)是等价的。
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
int x;
int k;
cin>>n;
cin>>k;
for(int i=2;i<=n;i++){
cin>>x;
k=__gcd(k,x);
}
cout<<1LL*k*n;
}
// 64 位输出请用 printf("%lld")
查看34道真题和解析
