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

首页 > 代码库 > 【学习整理】NOIP涉及的数论 [updating]

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

2024-08-11 12:46:52 218人阅读

扩展欧几里得

求二元一次不定式方程 $技术分享$ 的一组解。

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