GCD作为缩写意义有多种。它通常表示多核编程的解决方法，也有最大公约数（greatest common divisor，简写为gcd；或highest common factor，简写为hcf），此外它还是什么***什么的拼音缩写和游戏《鬼吹灯外传》的拼音缩写和“创意群总监”的英文缩写。在这里我讲一下GCD作为最大公约数（greatest common divisor，简写为gcd；或highest common factor，简写为hcf）时的一些计算方法。
GCD
Common GCD(I)
题目：给定两个数 $ A,B $ ，求他们的最大公约数
Example 1 ：
输入：4 9
输出：1
Example 2 ：
输入：3 9
输出：3
P.S. $ A,B<=1e6 $
这种题目范围比较小也比较简单可以直接暴力求出
/*
*@Author: ChenShou
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "
"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
//}
long long int a,b;
long long int ans=0;
scanf("%lld %lld",&a,&b);
if(a>b)swap(a,b);
for(long long int i=1;i<=a&&i<=b;i++){
if(a%i==0&&b%i==0)ans=i;
}
printf("%lld
",ans);
#ifdef DEBUG
printf("Time cost : %lf s
",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
Common GCD(II)
题目：输入N个数， (a_1,a_2,a_3, ...... , a_n) 求这N个数的最大公约数
Example 1 ：
输入：
5
2 4 6 8 10
输出：
2
Example 2 ：
输入：
2
7 49
输出：
7
P.S. P.S. $ a_i leq 10^9 ,N leq 10^8 $ 题目保证数据全随机化
这种题目数据范围比较大也题目难度比较简单可以直接暴力求出，并且注意到“数据全随机化”，这意味着在数据大而且多的情况下往往得到gcd=1，这样的话在gcd=1的时候直接退出程序可以节约一点时间
/*
*@Author: ChenShou
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "
"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;
long long int gcd(long long a,long long b){
return b == 0 ? a : gcd(b,a%b) ;
}
long long int gcd_(long long a,long long b){
return b == 0 ? a : gcd(b-a,a) ;
}
ll stein(ll a, ll b) {
if(!a)
return b;
if(!b)
return a;
if(!(a | 1) && !(b | 1))
return stein(a >> 1, b >> 1) << 1;
else if(!(a | 1))
return stein(a >> 1, b);
else if(!(b | 1))
return stein(a, b >> 1);
return stein(abs(a - b), min(a, b));
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
//}
long long N;
scanf("%lld",&N);
long long int num;
long long int ans=0;
while(N--){
scanf("%lld",&num);
if(!ans)ans=num;
else {
if(ans>num)swap(ans,num);
ans=__gcd(ans,num);
}
}
printf("%lld
",ans);
/*
for(long long int i=1;i<=a&&i<=b;i++){
if(a%i==0&&b%i==0)ans=i;
}
printf("%lld
",ans);
*/
//printf("%d
",gcd(a,b));
//printf("%d
",gcd_(a,b));
//printf("%d
",__gcd(a,b));
#ifdef DEBUG
printf("Time cost : %lf s
",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}