“CodeVS/1212”的版本间的差异

2014年8月17日 (日) 12:29的版本

题意

求最大公约数。

题解

第一反应是枚举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了，那么这就是所求解了。

反正古人很神奇，数论很神奇。

代码

#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;
}