<<<===码字不易，如有帮助，请点赞谢谢

题目描述

给定 $n$ 对正整数 $a_i,b_i$，请你求出每对数的最大公约数。

样例

2
3 6
4 6

3
2

小知识：最大公约数

公约数的定义：有两个数a和b，如果数d满足a是d的倍数且b是d的倍数，则我们称d为a和b的公约数，例如：3为6和9的公约数。

最大公约数的定义：有两个数a和b，如果数d是a和b的公约数且d最大，则我们称d为a和b的最大公约数，表示为d=(a,b)或者d=gcd(a,b)，例如：3为6和9的最大公约数。

算法1

(暴力枚举) $O(nm)（m为每组a_i,b_i中最小数的最大数）$

这题最简单的方法就是暴力枚举。
设$d=gcd(a,b)$，首先我们知道最大公约数$d$一定小于或等于数$a$与数$b$中的最小值（为什么：因为当$d>a$（假设$a$为最小的），那么$d$的倍数一定比$a$大），所以可以枚举$d$。

时间复杂度

每组测试数据中所需时间为每组$a_i,b_i$中最小数，则$n$组数据的时间复杂度就为$O(nm)（m为每组a_i,b_i中最小数的最大数）$。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
    int d;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        for(d=min(a,b);d>=1;d--)
            if(a%d==0&&b%d==0){
                cout<<d<<endl;
                break;
            }
    }
}

算法2

(质因数分解) $O(n\sqrt{m})（m为每组a_i,b_i中最小数的最大数）$

但是很明显，这种做法是过不了的，所以需要更快的做法。
我们可以把$a$与$b$质因数分解一下，设$v_p(x)（p为一个质数）$表示$x$中有多少个质因子$p$，那么$v_p(d)≤min(v_p(a),v_p(b))$，原因不用多说，读者自证不难，因为如果$v_p(d)>v_p(a)$，则有一些$p$无法整除，例如，$1000*3$一定不是$3^{2}$的倍数，多出来的一个$3$无法从$1000$里再找出一个$3$了。
那么我们就可以写出一个数学式子（前方高能）： $$d=\prod_{i=1}^{\infty} {p_i}^{min(v_{p_i}(a),v_{p_i}(b))}$$ （$p_i$表示第i个质数）
简而言之，就是找出$a$与$b$中最少含几个$p$求完幂后再相乘。
式子没看懂的看代码。

时间复杂度

质因数分解的时间复杂度为根号级别的，一共有$n$个数据，时间复杂度为$O(n\sqrt{m})（m为每组a_i,b_i中最小数的最大数）$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
    int i,d;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        d=1;
        for(i=2;i<=min(a,b)/i;i++){
            while(a%i==0&&b%i==0)a/=i,b/=i,d*=i;
            while(a%i==0)a/=i;
            while(b%i==0)b/=i;
        }
        if(a%b==0)d*=b;
        else if(b%a==0)d*=a;
        cout<<d<<endl;
    }
}

算法3

(辗转相除) $O(n\log_2{m})（m为每组a_i,b_i中最小数的最大数）$

但是,这种做法还是过不了，于是迎来了这题的正解——辗转相除法！

基本原理

定理：$gcd(a,b)=gcd(a-b,b)$
证明：

令d=gcd(a,b),a=xd,b=yd,gcd(x,y)=1.
则a-b=(x-y)d.
此时只需证gcd(x-y,y)=1.
若存在p>1使得x-y为p的倍数，且y为p的倍数，那么(x-y)+y也为p的倍数，即x为p的倍数，而gcd(x,y)=1，矛盾!
故gcd(x-y,y)=1.
故gcd(a,b)=gcd(a-b,b)

因为$gcd(a,b)=gcd(a-b,b)$，则$gcd(a,b)=gcd(a-2b,b)=gcd(a-3b,b)=…=gcd(a\mod b,b)$，故可将辗转相减变为辗转相除。

时间复杂度

不妨设$a>b$，若$a≥2b$，则$b≤a/2$，数据范围减一半；否则，$a<2b$，则$a\mod b=a-b≤a/2$，数据范围也减一半.
则数据范围不断除以$2$，时间复杂度为$O(n\log_2{m})（m为每组a_i,b_i中最小数的最大数）$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n;
int gcd(int a,int b)
{
    int r=a%b;
    if(!r)return b;
    return gcd(b,r);
}
int main()
{
    int i,d;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
}

算法4

(更相减损法)（也称二进制法，虽然跟二进制没有关系…） $O(n\log_2{m})（m为每组a_i,b_i中最小数的最大数）$

辗转相除法其实已经达到了速度的巅峰了，而且很好写，但是如果是求高精度的最大公因数，那这个代码复杂度就会飞速增长（也会导致一系列的问题，包括但不限于，TLE，MLE，SE，WA等），主要就是高精度模高精度会十分麻烦（感兴趣的读者可以自己逝一逝）。
这就是这个方法出现的意义，能以同样的复杂度解决高精度的问题。
这种方法主要就是在分类讨论：

1. a与b均为偶数，则$gcd(a,b)=2*gcd(a/2,b/2).$
2. a为奇数b为偶数，则$gcd(a,b)=gcd(a,b/2).$
3. a为偶数b为奇数，则$gcd(a,b)=gcd(a/2,b).$
4. a与b均为奇数，则$gcd(a,b)=gcd(a-b,b).$

时间复杂度

与辗转相除法类似，因为作者手懒，不想打了因为分析过程一样，就不讲了。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n;
int gcd(int a,int b)
{
    if(a<b)return gcd(b,a);
    if(a==b)return a;
    if(a%2==0&&b%2==0)return 2*gcd(a/2,b/2);
    if(a%2==0)return gcd(a/2,b);
    if(b%2==0)return gcd(a,b/2);
    return gcd(a-b,b);
}
int main()
{
    int i,d;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
}

附加题

SDOI2009（2009年山东省选）超级GCD

算法5

(STL) $O(n\log_2{m})（m为每组a_i,b_i中最小数的最大数）$

没啥好说的，直接一个__gcd就完了（在algorithm库里，当然万能头的同学就不用担心了），只有一点：考试的时候最好不要用带下划线的函数和一些不太常用的函数，因为可能会有一些小问题（例如：爆栈，不支持long long会将其强制转化为int导致溢出等等），所以考试时还是自己手打吧。

时间复杂度

底层实现就是辗转相除法，时间复杂度一样。

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,a,b;
    cin>>n;
    while(n--){
        cin>>a>>b;
        cout<<__gcd(a,b)<<endl;
    }
}

总结：所费时间：算法1、2：TLE；算法3：1128ms；算法4：1414ms；算法5：1129ms。