数学——数论(1)

先介绍一下部分常见数论知识点。
快速幂+裴蜀定理+扩展欧几里得算法+乘法逆元+费马小定理+线性筛。

//快速幂，p为模数，快速幂常解决a^b%p问题
int qpow(int a,int b){
    int res=1;
    int a%=p;
    while(b){
        if(b&1) res=(res*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return res;
}
//裴蜀定理：对于整数a,b,存在整数x,y使得ax+by=gcd(a,b)，其中gcd为a和b的最大公约数。     对于ax+by=c,存在整数解当且仅当c是gcd(a,b)的倍数。
//扩展欧几里得算法：求不定方程ax+by=c的整数解，或者求ax%p=1的整数解(乘法逆元)。(欧几里得算法求a和b最大公约数)
void exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
//乘法逆元：在模意义下，对于整数a和p，如果gcd(a,p)=1，则存在整数x使得ax%p=1，x即为a的乘法逆元。用于解决除法的模。
//费马小定理：p是质数，a^(p-1)≡1(mod p)，可化为a*a^(p-2)≡1(mod p),费马小定理扩展。(这里采用费马小定理求乘法逆元,同时涉及快速幂)
int inv(int a,int p){
    return qpow(a,p-2);
}
//线性筛：筛选质数,时间复杂度O(n)。
void sieve(int n){
    for(int i=2;i<=n;++i){
        if(!vis[i]){
            prime[++tot]=i;
        }
        for(int j=1;j<=tot&&i*prime[j]<=n;++j){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}