众所周知，最大公因数(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的最大公因数的值。
于是，你写出了一段递归求解的程序：
- void 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
- using namespace std;
- int main()
- {
- int a,b;
- cin>>a>>b;
- cout<<__gcd(a,b);
- return 0;
- }
但作为一名热爱共产党的新时代青少年，怎么能在gcd的前面加上两道杠呢？(你可以用键盘打出"gcd"试试)。
难道是退回第四境界呢？当然不行。作为一名合格的OIER，写的算法当然要及时更新迭代，不可以落后。
于是，你请出了#define语句(话说#define是真的好用)，用它写出了“货真价实”的gcd：
- #include
- #define gcd __gcd
- using namespace std;
- int main()
- {
- int a,b;
- cin>>a>>b;
- cout<<gcd(a,b);
- return 0;
- }
（无疾而终?)
点赞5个，更新下一期！