关于GCD

2019-07-23

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 \leq 1e^{6} $

这种题目范围比较小也比较简单可以直接暴力求出

/*
*@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 "\n"

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\n",ans);

#ifdef DEBUG
    printf("Time cost : %lf s\n",(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 "\n"

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\n",ans);
    /*
    for(long long int i=1;i<=a&&i<=b;i++){
        if(a%i==0&&b%i==0)ans=i;
    }
    printf("%lld\n",ans);
    */
    //printf("%d\n",gcd(a,b));
    //printf("%d\n",gcd_(a,b));
    //printf("%d\n",__gcd(a,b));
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}