簡單數(shù)論及算法選講

簡單數(shù)論及算法選講金靖華東師大二附中何為數(shù)論數(shù)論，是專門研究整數(shù)的純數(shù)學的分支，而整數(shù)的基本元素是素數(shù)（也稱質數(shù)），所以數(shù)論的本質是對素數(shù)性質的研究。數(shù)論被高斯譽為“數(shù)學中的皇冠”。按研究方法來看，數(shù)論大致可分為初等數(shù)論和高等數(shù)論。初等數(shù)論是用初等方法研究的數(shù)論，它的研究方法本質上說，就是利用整數(shù)環(huán)的整除性質，主要包括整除理論、同余理論、連分數(shù)理論?；靖拍罨靖拍?/p>

素數(shù)與合數(shù)

素數(shù)判定

1

boolisPrime(intn){2

if

(n==1)

return

false;3

else{4

for(inti=2;i*i<=n;i++)5

if

(n%i==

0)

return

false;6

return

true;7

}8

}例題：素因數(shù)分解

1

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

2

if(n%i==

0)

{3 cout<<n/i<<endl;4

break;5

}例題：[CF776B]Sherlockandhisgirlfriend

最大公約數(shù)和最小公倍數(shù)最大公約數(shù)和最小公倍數(shù)

1vector<int>factor(intx)

{2 vector<int>ret;3

for

(inti=

2;i*i<=x;

++i)4

while

(x%i==

0)

{5 ret.push_back(i);6 x/=i;7

}8

if

(x>

1)ret.push_back(x);9

returnret;10

}

1intpose(inta,intb){2 for(intx=2;x*x<=min(a,b);x++){3 while(a%x==0&&b%x==0){a/=x;b/=x;ans*=x;}4 while(a%x==0)a/=x;5 while(b%x==0)b/=x;6 }7if(a%b==0)ans*=b;8 elseif(b%a==0)ans*=a;9 returnans;10}

1

intEuclid(inta,intb){2

if

(b==0)

returna;3

else

returnEuclid(b,a%b);4

}1

intEuclid(inta,intb){2

return

(b==0)

?a:Euclid(b,a%b);3

}

例題：[BZOJ1876]SuperGCD

1

intgcd(intm,intn){2

if

(m==n)

returnm;3

if

(m<n)

returngcd(n,m);4

if

(m&

1

==

0)

5

return

(n&

1

==

0)?

2*gcd(m>>1,n>>1):gcd(m>>1,n);6

return

(n&

1

==

0)?gcd(m,n>>1):gcd(n,m-n);7

}

1 ans=1;2

for(inti=1;i<=n;i++){3 scanf("%d",&a[i]);4 ans=ans*a[i]/gcd(ans,a[i]);5

}6 printf("%d",ans);

兩數(shù)互素（互質）

模運算基本概念

剩余系

模運算

模運算

1

intmul_mod(inta,intb,intm){2 a%=m;b%=m;3

return

(int)((long

long)a*b%m);4

}冪取模

快速冪1

intpow_mod(inta,intn,intm){2

if(n==

0)

return

1;3

intx=pow_mod(a,n/2,m);4

long

longans=

(long

long)x*x%m;5

if(n%

2

==

1)ans=ans*a%m;6

returnans;7

}例題：NOIP2013D1T1

擴展歐幾里得算法裴蜀定理

例題：[BZOJ1441]

擴展歐幾里得算法

擴展歐幾里得算法

擴展歐幾里得算法1

intextend_gcd(inta,

intb,

int

&x,

int

&y)

{2

if

(b==

0)

{3 x=

1;y=

0;4

returna;5

}

6

else

{7

intret=extend_gcd(b,a%b,y,x);8 y-=x*

(a/b);9

returnret;10

}11

}擴展歐幾里得算法

擴展歐幾里得算法

例題：線性組合

例題：線性組合

例題：線性組合1

intmain(){

2 scanf("%d",&n);3 gcd[0]=0;4

for(inti=1;i<=n;i++)

{5 scanf("%d",&a[i]);6 gcd[i]=Euclid(gcd[i-1],a[i]);7

}8 scanf("%d",&c);9

if

(c%gcd[n]==0){

10 y[n]=c/gcd[n];11

for

(inti=n;i>1;i--)12 Extended_Euclid(gcd[i-1],a[i],gcd[i]*y[i],y[i-1],x[i]);

13 x[1]=y[1];14

for(inti=1;i<=n;i++)printf("%d",x[i]);15

}16

return

0;17

}逆元模

??

意義下乘法的逆

逆元

1

intinverse(inta,

intb)

{2

intx,y;3 exgcd(a,b,x,y);4

returnx;5

}

線性求逆元：遞推法

1

for

(inverse[1]

=

1,i=

2;i<=n;

++i)2 inverse[i]

=inverse[p%i]*(p-p/i)

%p;線性求逆元：倒推法

例題：組合數(shù)取模

容斥原理

各集合的交集容斥原理容斥原理容斥原理

錯排問題

錯排問題

歐拉函數(shù)歐拉函數(shù)

容斥原理求歐拉函數(shù)

容斥原理求歐拉函數(shù)

基于素因數(shù)分解求歐拉函數(shù)的算法1

inteuler_phi(intn){2

intres=n;3

for(inti=

2;i*i<=n;i++)

{4

if(n%i==

0)

{5 res=res/i*

(i-

1);

6

for

(;n%i==

0;n/=i);7

}8

}9

if

(n!=

1)res=res/n*

(n-

1);10

returnres;11

}

素數(shù)篩法埃拉托斯特尼篩法埃式篩法

埃式篩法1 #definemaxn10000002

boolisPrime[maxn+1];/*isPrime[i]true表示i為素數(shù)*/3

voideratos(intn){4

inti,j;5 isPrime[0]

=isPrime[1]

=

false;6

for(i=

2;i<=n;

++i)

7 isPrime[i]

=

true;

8

for(i=

2;i*i<=n;

++i)

9

if(isPrime[i]){

10

for(j=i*i;j<=n;j+=i)

11 isPrime[j]

=

false;12

}13

}篩法優(yōu)化素因數(shù)分解-1利用埃氏篩法可以快速實現(xiàn)素因數(shù)分解，只要在判定質數(shù)時記錄下每個數(shù)值的最小素因數(shù)即可。算法實現(xiàn)如下：1 #definemaxn10000002

boolisPrime[maxn+1];3

int

minFactor[maxn+1];

//記錄每個數(shù)的最小素因數(shù)的數(shù)組5

voideratos(intn){6

inti,j;7 isPrime[0]

=isPrime[1]

=

false;8 minFactor[0]

=minFactor[1]

=

-1;9

for(i=

2;i<=n;

++i)

{10 isPrime[i]

=

true;11 minFactor[i]

=i;

//初始化，表示還未找到最小的素因數(shù)12

}篩法優(yōu)化素因數(shù)分解-213

for(i=

2;i*i<=n;

++i)

{

14

if(isPrime[i]){15

for(j=i*i;j<=n;j+=i){16 isPrime[j]

=

false;17

if(minFactor[j]==j)

//如果此前尚未找到j的素因數(shù)，18

//那么將其設為i19 minFactor[j]

=i;

20

}21

}22

}23}篩法優(yōu)化素因數(shù)分解-324 vector<int>factor(intx)

{25 vector<int>ret;26

while(x>

1){27 ret.push_back(minFactor[n]);28 n/=minFactor[x];29

}30

returnret;31

}利用埃氏篩法，生成歐拉函數(shù)值的表1

inteuler[MAX_N];2

voideuler_phi2(){3

for

(inti=

0;i<MAX_N;i++)euler[i]

=i;4

for

(inti=

2;i<MAX_N;i++)

{5

if

(euler[i]

==i)

{6

for

(intj=i;j<MAX_N;j+=i)

7 euler[j]

=euler[j]

/i*

(i-

1);8

}9

}10

}

歐拉篩法（線性篩）

i=素數(shù)表篩除的數(shù)i=素數(shù)表篩除的數(shù)2{2}{4}13{2,3,5,7,11,13}{26,39}3{2,3}{6,9}14{2,3,5,7,11,13}{28}4{2,3}{8}15{2,3,5,7,11,13}{30,45}5{2,3,5}{10,15,25}16{2,3,5,7,11,13}{32}6{2,3,5}{12}17{2,3,5,7,11,13,17}{34}7{2,3,5,7}{14,21,35,49}18{2,3,5,7,11,13,17}{36}8{2,3,5,7}{16}19{2,3,5,7,11,13,17,19}{38}9{2,3,5,7}{18,27}20{2,3,5,7,11,13,17,19}{20}10{2,3,5,7}{20}21{2,3,5,7,11,13,17,19}{42}11{2,3,5,7,11}{22,33}22{2,3,5,7,11,13,17,19}{44}12{2,3,5,7,11}{24}.........歐拉篩法（線性篩）1

voidEuler_sieve(intn){2 memset(isprime,true,sizeof(isprime));3 prime[0]=0;4

for(inti=2;i<=n;i++){5

if

(isprime[i])prime[++prime[0]]=i;//把素數(shù)保存到素數(shù)表prime中6

for(intj=1;j<=prime[0]

&&i*prime[j]<=n;j++){7 isprime[i*prime[j]]=false;//篩除i*prime[j]8

if

(i%prime[j]==0)

break;9

//當i中含有素因子prime[j]時中斷循環(huán),確保每個數(shù)只被它的最小素因子篩除10

}11

}12

}素數(shù)相關定理費馬小定理

費馬小定理

使用費馬小定理來判定素數(shù)

歐拉定理

使用歐拉定理求逆元

1

intpowermod(inta,

intb,

intn){2

intret=

1;3

while

(b)

{4

if

(b&

1)ret=

(long

long)ret*a%n;5 a=

(long

long)a*a%n;6 b>>=

1;7

}8

returnret;9

}威爾遜定理

線性同余方程線性同余方程

線性同余方程組