CodeVS/1212

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
最大公约数	★☆☆☆☆	答案正确	100	2014/08/16 23:31:13	无

题意

求最大公约数。

题解

第一反应是枚举2~根号n，然后悲催的发现2^31-1。

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

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

凭着模糊的印象写了下居然AC了。嗯是这样的：

int gcd(int a,int b){//要求a>b
  if(a%b==0)return b;
  return gcd(b,a%b);
}

大概原理是，如果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代码已折叠 展开折叠内容
#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; }