gcd模板

gcd(欧几里得算法辗转相除法):

gcd ( a , b )= d ;

即 d = gcd ( a , b ) = gcd ( b , a mod b );以此式进行递归即可。

之前一直愚蠢地以为辗转相除法输进去时 a 要大于 b ,现在发现事实上如果 a 小于 b,那第一次就会先交换 a 与 b。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 1 #include<stdio.h>
 2 #define ll long long
 3
 4 ll gcd(ll a,ll b){
 5     return b==0?a:gcd(b,a%b);
 6 }
 7
 8 int main(){
 9     ll a,b;
10     while(scanf("%lld%lld",&a,&b)!=EOF){
11         printf("%lld\n",gcd(a,b));
12     //    printf("%lld\n",a>b?gcd(a,b):gcd(b,a));
13     }
14     return 0;
15 }

1
2
3
4
5
6
在原基础上改成循环之后的GCD:

1 ll gcd(ll a,ll b){
2     for(;a>0&&b>0;a>b?a%=b:b%=a);
3     return a+b;
4 }
在原基础上改成循环之后的GCD: