2019中山纪念中学夏令营-Day19 数论初步【GCD（最大公约数），素数相关】

关于GCD的一些定理或运用的学习：

2.二进制算法求GCD

思想：使得最后的GCD没有2（提前把2提出来）

代码实现：

 1 #include <cstdio>
 2 #define int long long
 3 int gcd(int x,int y)
 4 {
 5     int i,j;
 6     if(x == 0) return y;
 7     if(y == 0) return x;
 8     for(i=0;0==(x&1);++i)x>>=1;//x & 1 用来判断x是否为偶数
 9     for(j=0;0==(y&1);++j)y>>=1;//同理，用来消去x,y因子的2
10     if(j<i)i=j;
11     while(1)
12     {
13         if(x<y)x^=y,y^=x,x^=y;//交换x和y的值（等同于swap，只是速度比它快多了（位运算））
14         if(0==(x-=y))return y<<i;
15         while(0==(x&1))x>>=1;//等同于x = x / 2;
16     }
17 }
18 signed main()
19 {
20     int a,b;
21     scanf("%lld %lld",&a,&b);
22     printf("%lld",gcd(a,b));
23 }