题目描述

这题模板是辗转相除的思想，题解中却很少讲辗转相除的内容。所以就写下本篇辗转相除的介绍

例子：
假如需要求 1997 和 615 两个正整数的最大公约数,用辗转相除法，是这样进行的：
1997 / 615 = 3 (余 152) 余数152与被除数615比较，谁大谁作为除数
615 / 152 = 4(余7) 余数7与被除数152比较，谁大谁作为除数
152 / 7 = 21(余5) 5与7比较
7 / 5 = 1 (余2) 2与5比较
5 / 2 = 2 (余1) 1与2比较
2 / 1 = 2 (余0) 1与0比较，发现存在余0，直接取除数作为最大公约数
至此，最大公约数为1

可以看出辗转相除法的思想就是取余数与除数来实现的

代码对应

文中核心函数是这个
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
但是简单的看或许看不出为什么可以做到实现：0、选择被除数余除数，1、比较余数与除数，2、余0存在取除数的功能。

抽象难就换具象的试试。
假如a=615,b=1997
则可以看出1997？gcd(1997,615%1997):a
当b非0时，肯定是选择前者，而前者gcd(1997,615%1997)=gcd(1997,615)

在此，gcd(b,a%b)完成了第0、1项功能，就是当b非0时，gcd可以知道哪个大可以作为被除数，因为小数取余大数返回的是小数本身

当最后一直运算，运算到局部变量a=2,b=1时，
b=11？gcd(1,2%1):2，此时，可以看出虽然知道被除数是a=2，余数是b=1，但是其实执行的是5/2=2~~1这一步
继续运算下去，g(1,0)时
b=0?gcd(0,1%0):1;时
此时余数为0了，才能返回a=1,也就是除数a=1。

辗转相除原理

一开始，我想用离散的方法来做，但是没有解出来，还是给出思想。
离散数学的知识—————唯一分解定理
一个数可以由若干的质数乘积构成
a1=(2^c11)(3^c12)…(pk^c1k) p属于质数集，c属于自然数集
那么
a2=(2^c21)(3^c22)…(pk^c2k)
最大公约数呢，就是gcd(a1,a2)=(2^min(c11,c21))(3^min(c12,c22))…(pk^min(c1k,c2k))

网上的思想

若最大公约数为m1=a2
若a1/a2=s…y,
可以转换为a2,(a2*s+y)的最大公约数，a2可以被m1整除，y也能被m1整除。
若y不能被m1整除，则说明m1不是a2与a1的最大公约数。

所以再设最大公约数为m2=max(a2,y)。求出a2与y的最大公约数就表明求出了a1与a2的最大公约数，所以a2与y的最大公约数也是m2
继续上面的操作，直到y除以m2余0时，就表明，m2是最大公约数了。

然后我们可以看出，如果按这个算法下去y最后会为0时才能罢休，不会出现y非0还能被a2整除的情况，因为如果y非0还能被a2整除。那么他会被归到a2*(s+1)中

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
using namespace std;

int const N=1e5+10;
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
}