/*======================================================================
用递归的方法求最大公约数 。
原理：欧几里得定理。gcd（a,b）=gcd(b,a mod b).其中，a>b>=0.
=======================================================================*/

1 long long gcd(long long a,long long b)
2 {
3     return (b==0) ? a : gcd(b,a%b);
4 }

 1 long long gcd2(long long a, long long b)
 2 {
 3     int r;
 4     while(b != 0)
 5     {
 6         r=a%b;
 7         a=b;
 8         b=r;
 9     }
10     return a;
11 }