查看CodeVS/1212的源代码 ←CodeVS/1212

[[分类:简单数学问题]]
{{信息题|最大公约数|http://www.codevs.cn/problem/1212/|1|100}}
==题意==
求最大公约数。
==题解==
第一反应是枚举2~根号n，然后悲催的发现2^31-1。

然后悠悠地想起来还有更相减损术和辗转相除法这一说，必修三都忘光了- -

欸……高考前数学老师还特意复习了来着的。挖个地洞钻进去。

凭着模糊的印象写了下居然AC了。嗯是这样的：
<pre>
int gcd(int a,int b){//要求a>b
  if(a%b==0)return b;
  return gcd(b,a%b);
}</pre>
大概原理是，如果u|a且u|b那么u|(a%b)，直到b|a为止，那么b就是所求。

换句话说，如果u|a且u|b，假设a可以分成m份的u，b可以分成n份的u，a%b就是a去除好多倍的n份的u，剩下的一定还是好多份的u，就是u|(a%b)。

然后gcd(a,b)等价于gcd(b,a%b)，然后gcd的东西就越来越小。

直到最后b只有一份的u了，那么这就是所求解了。

反正古人很神奇，数论很神奇。
==代码==
{{折叠|1212.cpp代码已折叠
|<pre>
#include<cstdio>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
int gcd(int a,int b){
  if(a%b==0)return b;
  return gcd(b,a%b);
}
int main(){
  int a,b;
  scanf("%d%d",&a,&b);
  printf("%d",gcd(max(a,b),min(a,b)));
  return 0;
}
</pre>
|code1212}}