第四讲 数学知识

一、质数

(一) 试除法判定质数：$O(\sqrt n)$

bool is_prime(int x){
    if(x<2)return false;
    for(int i=2;i<=x/i;i++)
        if(x%i==0)return false;
    return true;
}

(二) 分解质因数：$O(\sqrt n)$

void divide(int n){
    for(int i=2;i<=n/i;i++)
        if(n%i==0){
            int s=0;
            while(n%i==0){
                n/=i;
                s++;
            }
            printf("%d %d\n",i,s);
        }
    if(n>1)printf("%d %d\n",n,1);
}

(二) 筛质数

埃氏筛法：$O(n \log \log n)$

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=i+i;j<=n;j+=i)st[j]=true;
        }
    }
}

线性筛法（欧拉筛法）：$O(n)$

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++){
            st[i*primes[j]]=true;
            if(i%primes[j]==0)break;
        }
    }
}

二、约数

(一) 试除法求约数：$O(\sqrt n)$

vector<int> get_divivors(int n){
    vector<int> res;
    for(int i=1;i<=n/i;i++)
        if(n%i==0){
            res.push_back(i);
            if(n/i>i)res.push_back(n/i);
        }
    sort(res.begin(),res.end());
    return res;
}

(二) 约数个数：$O(\sqrt n)$

原理

若 $n=\prod p_i^ {\alpha_i}$，则 $n$ 的约数个数为 $\prod (\alpha_i+1)$。

int solve(int n){
    unordered_map<int,int> primes;
    while(n--){
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x/=i;
                primes[i]++;
            }
        }
        if(x>1)primes[x]++;
    }
    LL res=1;
    for(auto prime:primes)
        res=res*(prime.second+1)%mod;
    return res;
}

(二) 约数之和：$O(\sqrt n)$

原理

若 $n=\prod p_i^ {\alpha_i}$，则 $n$ 的约数之和为 $\prod \sum_{j=0}^{\alpha _i} p_i^j$。

技巧

计算 $\sum_{j=0}^{\alpha _i} p_i^j$ 时，可以采用秦九昭算法，

即令 $t_n =\sum_{j=0}^n p_i^j$，

则 $t_n=p_it_{n-1}+1$。

int solve(int n){
    unordered_map<int,int> primes;
    while(n--){
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x/=i;
                primes[i]++;
            }
        }
        if(x>1)primes[x]++;
    }
    ll res=1;
    for(auto prime:primes){
        int p=prime.first,a=prime.second;
        ll t=1;
        while(a--)t=(t*p+1)%mod;
        res=res*t%mod;
    }
    return res;
}

(三) 最大公约数

欧几里得算法（辗转相除法）：$O(\log n)$

原理 $\gcd (a,b)=\gcd (b,a \mod b)$

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

三、欧拉函数

定义

$1$ 到 $N$ 中与 $N$ 互质的数个数被称为欧拉函数，记为 $\varphi (N)$。

(一) 求某个数的欧拉函数：$O(\sqrt n)$

原理

若 $N=\prod p_i^{\alpha _i}$，
则 $\varphi (N)=N\prod\frac{p_i-1}{p_i} =N\prod(1-\frac{1}{p_i})$。

int phi(int x){
    int res=x;
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            res=res/i*(i-1);
            while(x%i==0)x/=i;
        }
    }
    if(x>1)res=res/x*(x-1);
    return res;
}

(二) 筛法求 $1$ 到 $n$ 的欧拉函数：$O(n)$

原理

若 $p$ 为质数，则 $\varphi (p)=p-1$；
若 $p$ 为质数且 $p \mid i$，则 $\varphi(pi)=p\varphi(i)$；
若 $p$ 为质数且 $p \nmid i$，则$\varphi(pi)=\varphi(p)\varphi(i)=(p-1)\varphi(i)$。

int primes[N],cnt,phi[N];
bool st[N];
void get_eulers(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0){
                phi[primes[j]*i]=primes[j]*phi[i];
                break;
            }
            phi[primes[j]*i]=(primes[j]-1)*phi[i];
        }
    }
}

四、快速幂

(一) 快速幂：$O(\log n)$

int qpow(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1)res=(LL)res*a%p;
        k>>=1;
        a=(LL)a*a%p;
    }
    return res;
}

(二) 快速幂求逆元：$O(\log n)$

原理

欧拉定理

若 $\gcd(a,n)=1$，则 $a^{\varphi(n)} \equiv 1 (\mod n)$。

费马小定理

由欧拉定理可得，若 $p$ 为质数，则 $a^{p-1}\equiv 1(\mod p)$。

由费马小定理可得，当模数 $p$ 为质数时，$a^{p-2}$ 即为 $a$ 模 $m$ 的乘法逆元。

int qpow(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1)res=(LL)res*a%p;
        k>>=1;
        a=(LL)a*a%p;
    }
    return res;
}
ans=qpow(a,p-2,p);

五、扩展欧几里得算法

(一) 扩展欧几里得算法：$O(\log n)$

原理

裴蜀定理

$\forall x,y\in \mathbb {N_+},\exists a,b\in \mathbb {Z},s.t. ax+by=\gcd(x,y).$

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;
}

(二) 线性同余方程：$O(\log n)$

解方程 $ax\equiv b(\mod m)$

$$ax\equiv b(\mod m)$$ $$m\mid(ax-b)$$ $$ax-b=my$$ $$ax+my=b$$
令 $d=\gcd(a,m)$，由裴蜀定理可知，
若 $b\mid d$，则可用扩展欧几里得算法计算 $x$ 的值；
若 $b\nmid 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;
}
int d=exgcd(a,m,x,y);
if(b%d)puts("impossible");
else x=(LL)x*(b/d)%m;

六、中国剩余定理

Learning…

七、高斯消元

Learning…

八、求组合数

(一) 求组合数 I（多组询问）：$O(n^2)$

原理

组合数递推式：$$C_a^b=C_{a-1}^{b-1}+C_{a-1}^b$$

int c[N][N];
void init(){
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
            if(j)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
            else c[i][j]=1;
}

To Be Continue…