素数

hekaiyu · 2020-06-22 23:48:22 · 个人记录

数论基础---素数

素数

素数又叫质数，指只包含两个因数的正整数（小学好像是这么定义的）其因子只有1 和本身。所含因子个数大于 2 的称为合数。特殊的，根据定义 1 既不是素数也不是合数。常见的素数有 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47\cdots\cdots (列举50以内的).

素数判定

对一个范围比较小的素数，我们可以暴力枚举因子进行判断

int zs(int n){
    if(n==1)return 0;//特判两个数
    if(n==2)return 1;
    if(n>2){
        for(int i=2;i*i<=n;i++){//显然枚举到根号a就够了
            if(n%i==0)//有其他因子
            return 0;//0为不是，1为是
        }
        return 1;
    }
}

以上代码时间复杂度为 O(\sqrt n )

有时我们也会预处理，生成素数表来判断素数；通常使用线性筛素数来生成。

P3383 【模板】线性筛素数

void make_prime(){
    memset(x,1,sizeof(x));
    x[0]=false;
    x[1]=false;//初始化
    int head=0;
    for(int i=2;i<=n;++i){
        if(x[i]){
            y[++head]=i;//记入到质数表
            for(int k=i*i/*直接过滤之前筛过的*/;k<=n;k+=i)x[k]=false;//质数倍数肯定是合数
        }
    }
}

以上为Eratosthenes筛法，时间复杂度接近线性，为 O(n\log\log n) 但并不能解决模板题。因为会重复筛合数，所以我们还需继续优化成线性。

考虑到一个合数可以分为一个质数与一个质数或合数的乘积。

void make_prime(){
    memset(x,1,sizeof(x));
    x[0]=false;
    x[1]=false;
    int head=0;
    for(int i=2;i<=n;++i){
        if(x[i])y[++head]=i;
        for(int j=1;j<=head&&i*y[j]<=n/*利用之前的素数表*/;++j){
            x[i*y[j]]=false;//防止重复筛
            if(!(i%y[j]))break;//关键步骤：保证每个合数只被筛一次，确保线性
        }
    }
}

时间复杂度就是 O(n) 了。

素数相关定理

唯一分解定理

对于一个整数a(a>1) 那么 a 一定可以表示为若干个素数的乘积且形式唯一。即 a=p_1^{k_1}\times p_2^{k_2}\times\cdots\times p_i^{k_i}。

例 1260=2^2\times3^2\times5\times7。

约数个数与约数和公式

约数个数=(1+k_1)\times(1+k_2)\times\cdots\times(1+k_i)（这显然可以通过乘法原理计算）

约数和=(1+p_1^1+p_1^2+\cdots+p_1^{k_1})\times(1+p_2^1+p_2^2+\cdots+p_2^{k_2})\times\dots\times(1+p_i^1+p_i^2+\cdots+p_i^{k_i})

威尔逊定理

若 p 为素数，则 (p-1)!\equiv -1\pmod p （ n! 表示 n 的阶乘）

逆定理同样成立，若 (p-1)!\equiv -1\pmod p 则 p 为素数）

费马定理

若 p 为质数， a 为整数，且 p,a 互质，则 a^{(p-1)}\equiv 1\pmod p

\color{Red}\text{费马小定理：} $ $a^p\equiv a\pmod p

（两边同时成 a 得到）。

因此在模 p 意义下 a的逆元是 a^{p-2}，直接快速幂计算即可。

欧拉函数

定义：对于正整数 n，欧拉函数是小于等于 n 的树中与 n 互质的数的数目，记为 \phi(n) .

引理：

如果 p 为质数，则：\phi(p)=p-1。
如果 p 为质数，则：\phi(p^a)=(p-1)*p^{a-1} 。
如果 a,b 互质，则：\phi(a\times b)=\phi(a)\times\phi(b)（所以欧拉函数是积性函数）

计算公式：\phi=n\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times\cdots\times(1-\frac{1}{p_i})

欧拉定理：若 a 与 m 互质则 a^{\phi(m)}\equiv 1\pmod m

扩展欧拉定理 对于任意的 a,m 满足: 当 b\ge \phi(m) 时 a^{(b\%\phi (m)+\phi(m))}\equiv a^b\pmod m

P5091 【模板】扩展欧拉定理
P4139 上帝与集合的正确用法
欧拉筛

P2158 [SDOI2008]仪仗队（这是一道金典的欧拉筛板子题）

我们利用计算公式来进行筛选

代码如下：

void phi_build(int n,int *phi){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!phi[i])
            for(int j=i;j<=n;j+=i){
                if(!phi[j])phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
    }
}

时间复杂度不是很好证明，给个结论为 O(n\log n)

P2398 GCD SUM

上面的筛法蛮快的，但其实欧拉函数是有线性筛的。

需要利用以下性质：

当 p\mid i 时 \phi(i\times p)=p\times \phi(i)

当 p\nmid i 时 \phi(i\times p)=(p-1)\times \phi(i) 。

然后配上我们的线性素数筛，代码如下：

void build(){
    phi[1]=1;check[1]=0;
    for(int i=2;i<=n;i++){
        if(!check[i])phi[i]=i-1,prime[++head]=i;
        for(int j=1;j<=head&&prime[j]*i<=n;j++){
            check[prime[j]*i]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }

模板应用：P2568 GCD

Pollard\ Rho 算法求大整数因子

此部分好像不是很常用，但还是了解一下（跳过也没什么事）。

P4718 【模板】Pollard-Rho算法（先看看模板，了解下时间复杂度，快但是模板题难度...，知道为什么很少用了吧（代码长（成为码农），复杂度不稳定（比朴素的快）））。

由于很少用，使用就给个代码吧，有兴趣自行百度,以后有时间再补充。

以下代码非模板题答案：

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
const int times=10;
typedef long long ll;
ll ct,cnt;
ll fac[maxn],num[maxn];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll mul(ll a,ll b,ll m){
    ll ans=0;
    a%=m;
    while(b){
        if(b&1)ans=(ans+a)%m;
        b>>=1;
        a=(a+a)%m;
    }
    return ans; 
}
ll quick_mod(ll a,ll b,ll m){
    ll ans=1;
    a%=m;
    while(b){
        if(b&1)ans=mul(ans,a,m);
        b>>=1;
        a=mul(a,a,m);
    }
    return ans; 
}
bool Miller_Rabin(ll n){
    if(n==2)return true;
    if(n<2||!(n&1))return false;
    ll m=n-1;
    int k=0;
    while((m&1)==0){
        k++;
        m>>=1;
    }
    for(int i=0;i<times;i++){
        ll a=rand()%(n-1)+1;
        ll x=quick_mod(a,m,n);
        ll y=0;
        for(int j=0;j<k;j++){
            y=mul(x,x,n);
            if(y==1&&x!=1&&x!=n-1)return false;
            x=y;
        }
        if(y!=1)return false;
    }
    return true;
}
ll pollard_rho(ll n,ll c){
    ll i=1,k=2;
    ll x=rand()%(n-1)+1;
    ll y=x;
    while(1){
        i++;
        x=(mul(x,x,n)+c)%n;
        ll d=gcd((y-x+n)%n,n);
        if(1<d&&d<n)return d;
        if(x==y)return n;
        if(i==k){
            y=x;
            k<<=1;
        }
    }
}
void find(ll n,int c){
    if(n==1)return ;
    if(Miller_Rabin(n)){
        fac[ct++]=n;
        return;
    }
    ll p=n;
    ll k=c;
    while(p>=n)p=pollard_rho(p,c--);
    find(p,k);
    find(n/p,k);
}
int main(){
    int t;long long n;
    scanf("%d",&t);
    while(t--){
        scanf("%lld",&n);
        ct=0;
        find(n,120);
        sort(fac,fac+ct);
        num[0]=1;
        int k=1;
        for(int i=1;i<ct;i++){
            if(fac[i]==fac[i-1])++num[k-1];
            else{
                num[k]=1;
                fac[k++]=fac[i];
            }
        }
        cnt=k;
        for(int i=0;i<cnt;i++){
            cout<<fac[i]<<" "<<num[i]<<" ";//输出因子和次数
        }
        cout<<endl;
    }   
    return 0;
}

模板题很毒，反正我是卡不过去了。