【学习整理】NOIP涉及的数论 [updating]

2021-10-16 21:20:34

扩展欧几里得

求二元一次不定式方程的一组解。

int exgcd(int a,int b,int &x,int &y)

{

    int t;

    if(!b) {x=1;y=0;return a;}

    t=exgcd(b,a%b,y,x);

    y-=(a/b)*x;

    return t;

}

线性筛质数

维护一个质数表。对于每个数，从小到大枚举所有质数，将打上标记。如果，停止枚举。

void getprime()

{

    int i,j;

    for(i=2;i<=n;i++)

    {

        if(!b[i]) prime[++tot]=i;

        for(j=1;j<=tot&&i*prime[j]<=n;j++)

        {

            b[i*prime[j]]=true;

            if(!i%prime[j]) break;

        }

    }

}

线性求逆元

逆元的定义：称x是a在模b意义下的逆元，可理解为。

给定一个质数，求出至的逆元。

证明：

费马小定理

若是质数，则

证明：

因为，所以.

线性求欧拉函数

欧拉函数的定义：小于等于的正整数中与互质的数的个数。

设为最小的质数，。在线性筛中，被筛掉。

当时，。

void getphi()

{

    int i,j;

    phi[1]=1;

    for(i=2;i<=n;i++)

    {

       if(!b[i])

       {

           prime[++tot]=i;

           phi[i]=i-1;

       }

       for(j=1;j<=tot;j++)

       {

           if(i*prime[j]>n)  break;

           b[i*prime[j]]=true;

           if(i%prime[j]==0)

           {

               phi[i*prime[j]]=phi[i]*prime[j];

               break;

            }

            else  phi[i*prime[j]]=phi[i]*(prime[j]-1);

       }

     }

}

欧拉定理

若，则。

证明：

记 , 记为到中与互质的数。

由消去律得

Miller-Rabin算法素数测试

记

在中随机选取一个整数，如果或 , 那么我们认为n是质数。

错误率不超过1/4，重复若干次即可。

long long mod_mul(long long,long long,long long);

long long mod_exp(long long,long long,long long);

bool miller_rabbin(long long n)

{

    int i,j,t;

    long long a,x,y,u;

    if(n==2)return true;

    if(n<2||!(n&1)) return false;

    t=0;u=n-1;

    while((u&1)==0) t++,u>>=1;

    for(i=1;i<=tim;i++)

    {

        a=rand()%(n-1)+1;

        x=mod_exp(a,u,n);

        for(j=0;j<t;j++)

        {

            y=mod_mul(x,x,n);

            if(y==1&&x!=1&&x!=n-1) return false;

             x=y;

        }

        if(x!=1) return false;

    }

    return true;

}

long long mod_mul(long long a,long long b,long long mod)

{

    long long res=0;

    while(b)

    {

        if(b&1) res=(res+a)%mod;

        a=(a+a)%mod;

        b>>=1;

    }

    return res;

}

long long mod_exp(long long a,long long b,long long mod)

{

    long long res=1;

    while(b)

    {

        if(b&1) res=mod_mul(res,a,mod);

        a=mod_mul(a,a,mod);

        b>>=1;

    }

    return res;

}