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

扩展欧几里得

求二元一次不定式方程 $ax+by=gcd(a,b)$ 的一组解。

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

线性筛质数

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

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

线性求逆元

逆元的定义： $ax$equiv$1(mod$quad$b)$ 称x是a在模b意义下的逆元，可理解为 $a*a^{-1}$equiv$1(mod$quad$b)$ 。

给定一个质数 $p$ ，求出 $1$ 至 $p-1$ 的逆元。

$a[i]=-[p/i]*a[p\,mod$\,$$\,$i]$

证明：

$-i*$lfloor$cfrac{p}{i}$ floor$+(p\,mod$\,$$\,$i) $equiv$ 0(mod$quad$p)$

$-i*$lfloor$cfrac{p}{i}$ floor$ $equiv$ (p\,mod$\,$$\,$i)(mod$quad$p)$

$i*(-$lfloor$cfrac{p}{i}$ floor$*a[p\,mod$\,$$\,$i]) $equiv$ 1(mod$quad$p)$

费马小定理

若 $p$ 是质数，则 $a^{p-1}$equiv$1(mod$quad$p)$

证明：

因为 $gcd(a,p)=1$ ，所以 ${a,2a,$cdots$,(p-1)a}={1,2,$cdots$,p-1}$ .

$a*2a*$cdots$*(p-1)a$equiv$1*2*$cdots$*(p-1)$

$a^{p-1}*(p-1)!$equiv$(p-1)!$

$a^{p-1}$equiv$1$

线性求欧拉函数

欧拉函数 $$phi$(x)$ 的定义：小于等于 $x$ 的正整数中与 $x$ 互质的数的个数。

$phi(x)=egin{cases}1&x=1\x-1&x;is;prime\ xprod_{i=1}^{x}(frac{p_{i}-1}{p_{i}})&x=p_1^{a_1}$ imes$p_2^{a_2}$ imesdots imes$p_k^{a_k}\end{cases}$

设 $p$ 为 $x$ 最小的质数， $x'=x/p$ 。在线性筛中， $x$ 被筛 $p$ imes$x'$ 掉。

当 $x';mod;p ot=0$ 时， $phi(x)=p$ imes$x' imes(frac{p-1}{p})prod_{i=1}^{k'}(frac{p_{i}-1}{p_{i}})=(p-1) imesphi(x')$ 。

当 $x';mod;p=0$ 时， $phi(x)=p$ imes$x' imesprod_{i=1}^{k'}(frac{p_{i}-1}{p_{i}})=p imesphi(x')$ 。

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

欧拉定理

若 $gcd(a,p)=1$ ，则 $a^{phi(p)}$equiv$1(mod$quad$p)$ 。

证明：

记 $phi(p)=n$ , 记 $x_1,x_2,$dots$,x_{phi（p）}$ 为 $1$ 到 $p-1$ 中与 $p$ 互质的数。

${x_1,x_2,$dots$,x_{phi(p)}}={a*x_1\,mod\,p,a*x_2\,mod\,p,$dots$,a*x_{phi(p)}\,mod\,p}$

$x_1*x_2*$dots$*x_{phi(p)}$equiv$ a^{phi(p)}*x_1*x_2*$dots$x_{phi(p)}(mod$quad$p)$

由消去律得 $a^{phi(p)}$equiv$1(mod$quad$p)$

Miller-Rabin算法素数测试

记 $n=a*2^b$

在 $[1,n)$ 中随机选取一个整数 $x$ ，如果 $x^a$equiv$1(mod$quad$n)$ 或 $x^{a*2^i}$equiv$-1(mod$quad$n)$quad$(0$leq$i<b)$ , 那么我们认为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;
}

Pollard-rho算法分解合数

中国剩余定理

解方程组 $x$equiv$a_i(mod$quad$p_i)$ 其中 $p_i$ 两两互质。

大步小步法(BSGS)及其拓展

求最小的 $x$ 使得 $a^x$equiv$b(mod$quad$p)$ ， $p$ 为质数。

莫比乌斯反演

已知 $F(i)=sum_{d|i}^{}$\,$f(i)$ 求 $f(i)$ 。

原根的基本性质

拉格朗日定理

二次剩余