前言 

        众所周知，最大公因数(gcd)是C++程序中第二常见的函数(仅次于判素数)。正因此，一个简单的gcd也能被不同的OIER写出不同的“境界”。

        话不多说，直接开始！

---

第一境界：暴力枚举！

        如果你是一个连while循环都没写过的超级蒟蒻(天南星科植物魔芋属植物)，那么你该怎么写判最大公因数程序？

        答案很简单：暴力枚举！

        我们可以用循环变量i直接从A，B中的小值直接反向枚举到1，如果能同时被A，B整除，直接输出i就行了。

        这样写虽然长(其实也不是很长)，但也是最直白的思路了：

int gcd(int a,int b)
{
	for(int i=min(a,b);i>=1;i--)
		if(a%i==0&&b%i==0) return i;
}

         但这样写的时间复杂度是O(min(a,b))，因此一旦A，B都特别大的时候(比如说都是2的31次方)，这种方法的运行速度将会比乌龟还慢，自然会时间超限(TLE)。

---

第二境界：辗转相除法

        很快，你就学会了while循环，同时也去百度上搜索了辗转相除法。

        辗转相除法就是定义一个变量R来储存A模B的值，再将A的值设为B，B的值设为R。以此类推，直到B=0为止。然后直接输出A就行了。

        这样写虽然长了一点，但是时间复杂度获得了飞跃性的提升：

int gcd(int a,int b)
{
	while(b>0)
	{
		int r=a%b;
		a=b;b=r;
	}
	return a;
}

        作为一名初学者，会这段程序就够了(bushi)。 

---

第三境界：递归

       一个寒假过去了，曾经的那名蒟蒻终于学会了递归。

        你发现，用递归写最大公因数又快了很多。

        用递归写最大公因数，还是基于辗转相除法。这样写，当A模B等于0时，返回B；否则返回递归求解B和A模B的最大公因数的值。

        于是，你写出了一段递归求解的程序：

int gcd(int a,int b)
{
    if(a%b==0) return b;
    else return gcd(b,a%b);
}

        可这样写在OJ上没有通过。奇怪，百度上不是那么写的吗？

        事实上，根据辗转相除法的性质，应该是在B等于0是返回此时A的值，而不是在当A模B等于0时返回B的值。

        你把程序改了一下，果然通过(AC)了这道题目：

int gcd(int a,int b)
{
	if(b==0) return a;
	else return gcd(b,a%b);
}

---

第四境界：三元组

        你在《信息学奥赛一本通》中学到了有关三元组的知识。

        "啊？三元组？这似乎能运用到gcd上啊。"

        事实上，三元组在时间复杂度上与递归相比并没有变快。但是，使用三元组，原本两行的代码变成了一行。

        于是，求最大公因数的算法由两行变成了一行：

int gcd(int a,int b)
{return (b==0?a:gcd(b,a%b);}

---

第五境界：编译器自带函数！

        前段时间，你在一篇题解上发现了__gcd这个编译器自带函数。

        于是你一口气写出了判最大公因数的整个程序(真的只用了一口气的时间):

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	cout<<__gcd(a,b);
	return 0;
}

---

第六境界：从__gcd变回gcd

        但作为一名热爱共产党的新时代青少年，怎么能在gcd的前面加上两道杠呢？(你可以用键盘打出"gcd"试试)。

        难道是退回第四境界呢？当然不行。作为一名合格的OIER，写的算法当然要及时更新迭代，不可以落后。

        于是，你请出了#define语句(话说#define是真的好用)，用它写出了“货真价实”的gcd：

#include<bits/stdc++.h>
#define gcd __gcd
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	cout<<gcd(a,b);
	return 0;
}

---

后记

在2023.10.19更改了之前程序的错误。