程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 【學習整理】NOIP涉及的數論 [updating],noipupdating

【學習整理】NOIP涉及的數論 [updating],noipupdating

編輯:C++入門知識

【學習整理】NOIP涉及的數論 [updating],noipupdating


擴展歐幾裡得

求二元一次不定式方程 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$\times$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 ,求出 1p-1的逆元。

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

證明:

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

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

i*(-$\lfloor$\cfrac{p}{i}$\rfloor$*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)=\begin{cases}1&x=1\\x-1&x\;is\;prime\\
x\prod_{i=1}^{x}\(\frac{p_{i}-1}{p_{i}}\)&x=p_1^{a_1}$\times$p_2^{a_2}$\times\dots\times$p_k^{a_k}\\\end{cases}

px 最小的質數,x'=x/p。在線性篩中,x被篩p$\times$x'掉。

x'\;mod\;p\not=0時,\phi(x)=p$\times$x'\times\(\frac{p-1}{p}\)\prod_{i=1}^{k'}\(\frac{p_{i}-1}{p_{i}}\)=(p-1)\times\phi(x')

x'\;mod\;p=0時,\phi(x)=p$\times$x'\times\prod_{i=1}^{k'}\(\frac{p_{i}-1}{p_{i}}\)=p\times\phi(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)}1p-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)

 

 

原根的基本性質

 

 

拉格朗日定理

 

 

二次剩余

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved