数论

欧几里得算法 筛法求素数（埃氏筛、欧拉筛） 裴蜀定理板子

欧几里得(辗转相除法)

求a，b的最大公因数

gcd(a,b) = gcd(b,a%b) = ….. 直到(a,b)中b为0，那么结果就为a

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

筛法求素数

埃氏筛

从2开始的 x ，划掉每个x的倍数，优化一下可以从x^2^开始划

int primes[N],cnt;
bool st[N];//初始为false，true表示被筛掉了，最后为false的都是质数
for(int i=2; i<=n ;i++){
    if(!st[i]){
        primes[cnt++] = i;
    	for(int j=i*i; j<=n; j++) st[i]=true;
    }
}

欧拉筛

• 每个合数只被划掉一次，而且是被它的最小质因子划掉的 (原理是：每个合数都有一个<= sqrt(x) 的质因子 )
  • 由于被它的最小质因子划掉的，因此还可以求每个数的最小质因子
• 筛的过程，为了避免重复筛
  • 对于每个数x，乘上 <= x的最小质因子的质数，就可以保证不重复筛

int primes[N],cnt;
bool st[N];
void get_primes(int n){
    for(int i=2; i<=n; i++){
        if(!st[i]) primes[cnt++] = i;
        for(int j=0; primes[j]*i<=n;j++ ){//此时primes[]数组里面的都是 <= i的
            int t = primes[j]*i ;
            st[t] = true;//筛掉
            if(i % primes[j] == 0 ) break;//primes[j]就是最小质因子，因为前面两行代码已经实现了乘primes[j],直接退出
        }
    }
}

裴蜀定理(扩展欧几里得算法)

(a,b) = d

裴蜀定理可以求出一组x，y 使得 d = ax0 + by0

并且只要求出满足的一组解x，y，就可以求出所有解

a’ = a/d b’ = b/d

x = x0 + kb’ y = y0 - ka’

运用

(a,b) = (b,a%b) =… = d

因此 b*y + (a % b) * x = d

即 by + (a - a/b * b ) * x = ax + (y-a/b * x ) * b = d

=> x’ = x y’ = y - a/b*x (b = 0 时停止)

//exgcd可以找出满足的 d = ax + by 中的x，y并且返回d
int exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a%b, y, x);
    y -= a / b * x;
    return d;
}