学习笔记 - 数论/数学 - 花式求最大公因数

zjcOvO · 2021-08-15 23:18:45 · 个人记录

一组整数的最大公约数，是指所有公约数里面最大的一个，记为 \gcd(...) 。

两个数的最大公约数

欧几里得算法

指路 ，复杂度 O(\log n)

欧几里得优化 -> Stein算法

已知 a,b，求 \gcd(a,b)

先把 a,b 都变成奇数，记录 a,b 中含有多少公共的 2，最后乘回来。

类似欧几里得算法进行辗转相减/相除，此过程中得到的 a,b 可以放心的除以 2。

代码实现

1. 欧几里得 - 最朴素的递归

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

2. 欧几里得 - 不用递归

   int gcd(int a,int b){
   if(b) while((a%=b)&&(b%=a));
   return a+b;
   }

3. Stein算法 - 非位运算版

   int gcd(int a,int b){ int c=0;
   if(a==0||b==0) return a+b;
   while(a%2==0&&b%2==0){a/=2;b/=2;c++;}
   while(a%2==0)a/=2; while(b%2==0)b/=2;
   if(a<b) swap(a,b);
   while(a%=b){while(a%2==0)a/=2;if(a<b)swap(a,b);} //此处括号中a%=b 可以换为 a=(a-b)/2，但亲测int下换了会变慢一点点
   return b<<c;
   }

4. Stein算法 - 位运算版

int 下，改成位运算并不能使代码变快，反而使代码更长，可读性更差，不建议使用。

但倘若想求高精\gcd，且写了 2^k 压一位的高精模板的话，也许比非位运算版能快一些。

int gcd(int a,int b){int c=0;
    if(a==0)return b;if(b==0)return a;
    while((!(a&1))&&(!(b&1))){a>>=1;b>>=1;c++;}
    while((!(a&1)))a>>=1; while((!(b&1)))b>>=1;
    if(a<b) swap(a,b);
    while(a=((a-b)>>1)){while((!(a&1)))a>>=1;if(a<b)swap(a,b);}//用高精的话换了快
    return b<<c;
}