数学模板

试除法判定质数

bool is_prime(int x){ //判断x是否是质数
    if(x<2) return false; //非质数
    for(int i=2;i<=x/i;i++)
        if(x%i==0) return false; //非质数
    return true; //质数
}

试除法分解质因数

void divide(int x){ //分解x的质因数
    for(int i=2; i*i<=x;i++ )
        if(x%i==0){  //i一定会是质数
            int s=0;//s用于统计因子i的个数
            while(x%i==0) x/=i,s++;
            cout<<i<<' '<<s<<endl;
        }
    if(x>1) cout<<x<<' '<<1<<endl;
}

朴素筛法求素数（埃氏筛）

int p[N],cnt;//p[]存储所有素数,cnt质数个数
bool v[N]; //v[x]标记x是否被筛掉
void get_primes(int n){
    for (int i=2;i<=n;i++){
        if(v[i]) continue;
        p[++cnt]=i; //存储质数
        for(int j=i+i;j<=n;j+=i)
            v[j]=true; //标记j为合数
    }
}

线性筛法求素数（欧拉筛）

int p[N],cnt;//p[]存储所有素数,cnt质数个数
bool v[N];  //v[x]标记x是否被筛掉
void get_primes(int n){
    for (int i=2;i<=n;i++ ){
        if (!v[i]) p[++cnt]=i;//存储质数
        for (int j=1;p[j]*i<=n;j++ ){
            v[p[j]*i]=true;//标记p[j]*i为合数
            if(i%p[j]==0) break;
        }
    }
}

试除法求所有约数

vector<int> get_divisors(int x){
    vector<int> res;
    for(int i=1;i<=x/i;i++ )
        if(x%i==0){ //i是x的因子
            res.push_back(i);  //存储因子i
            if(i!=x/i) res.push_back(x/i); //存储因子x/i
        }
    sort(res.begin(),res.end()); //因子从小到大排序
    return res;
}

约数个数和约数之和

如果 N=p1c1*p2c2*...*pkck   //唯一分解定理
约数个数： (c1+1)*(c2+1)*...*(ck+1)
约数之和： (p10+p11+...+p1c1)*...*(pk0+pk1+...+pkck)

欧几里得算法（辗转相除法）

int gcd(int a, int b){  //辗转相除法
    return b?gcd(b,a%b):a;
}

快速幂

//求 mk mod p，时间复杂度 O(logk)。
int qmi(int m,int k,int p){
    int res=1,t=m;
    while(k){
        if(k&1) res=res*t%p;
        t=t*t%p;
        k>>=1;
    }
    return res;
}