acm入門第二講數論

1、數論主要內容：篩法求素數歐幾里德算法求最大公約數擴展歐幾里德算法模線性方程的解法模線性方程組整除與約數對于整數d和a，如果存在整數k使得a=k*d，我們就說d能整除a ，記為d|a（讀作d整除a）例如，因為24=3*8所以3能整除24，記為3|24如果d|a，并且d0，則稱d是a的約數。例如，24的約數有1、2、3、4、6、8、12、24.每個整數a都可以被其平凡約數1和a整除，a的非平凡約數也稱為a的因子。素數與合數對于某個大于1的整數a，如果它僅有平凡約數1和a則稱a是素數（或質數）。否則稱a是合數。素數有 2，3，5，7，11，13，17，19，23，29，素數有無窮多個素數的應用唯一素

2、因子分解定理：合數a僅能以一種方式，寫成如下的乘積形式：a=p1e1p2e2prer 其中pi為素數，p1p2pr，且ei為正整數如果正整數n分解質因子的結果為n=p1e1p2e2prer， 則n的約數個數為: (e1+1)*(e2+1)*(er+1)。所有約數之和為：(1+p1+p12+p1e1)*(1+p2+p22+p2e2) *(1+pr+pr2+prer)素數的判定對于大于1的正整數a，如果a具有小于或等于sqrt（a）的素因子，則a為合數，否則a為素數。因此，可用區(qū)間2,sqrt(a)內的數去試除a，只要有一個數能整除a ，則a為合數，否則a為素數。這種判斷素數的方法就是試除法。復雜

3、度O(sqrt(n).試除法IsPrime(a)for(i=2;i*isqrt(n)時篩中剩下的數就已經都是素數了。篩法求素數/用數組primeMAXN記錄是否為素數；/primei為0表示i為素數，否則為合數int primeMAXN=0;for(i=2;i*i=n;i+)if(primei=0)for(j=i+i;j=n;j+=i)primej=1;因式分解tn=n;for(i=2;i*i1)/存在大于sqrt(n)的素因子p+cnt=tn;ecnt=1;例題一：Goldbachs Conjecture(TOJ1171)題目描述：對于輸入的偶數n(6n1000000),是否可以表示為兩個奇

4、素數之和。如果可以表示，輸出表達式，否則輸出Goldbachs conjecture is wrong. 例題一：Goldbachs Conjecture(TOJ1171)Sample Input8 20 42 0 Sample Output8 = 3 + 5 20 = 3 + 17 42 = 5 + 37 例題一：Goldbachs Conjecture(TOJ1171)假設兩個奇素數中較小的一個為a， 讓a從2取到n/2，如果a取到某個值時a與n-a都為素數，則此時的a與n-a的值便是所求。如果最終找不到滿足條件的a則無解，輸出“Goldbachs conjecture is wrong.

5、”即可。 因此可以用篩法預先計算出21000000內的素數，然后判斷即可最大公約數與最小公倍數d是a的約數并且也是b的約數，則d是a與b的公約數。兩個不同時為0的整數a和b的最大公約數表示為gcd(a, b)。如果d既能被a整除也能被b整除，則d是a與b的公倍數，a與b公倍數中最小的叫a與b的最小公倍數，表示為lcm(a,b).gcd(a,b)*lcm(a,b)=a*b最大公約數為1的兩個數互質最大公約數的求法GCD遞歸定理：對任意非負整數a和任意正整數b，有gcd(a, b) = gcd(b, a mod b) 。最大公約數的求法歐幾里德算法（也叫輾轉相除法）：EUCLID(a, b)if

6、b = 0then return aelse return EUCLID(b, a % b)例如:gcd(18,24)=gcd(24,18)=gcd(18,6)=gcd(6,0)=6算法復雜度O(lg(b)歐幾里德算法int gcd(int a,int b)if(b=0)return a;return gcd(b,a%b);擴展歐幾里德算法通過歐幾里德算法我們不僅能求出a與b的最大公約數，還可以改寫歐幾里德算法，求出整數x和y 使得gcd(a,b)=ax+by擴展歐幾里德算法設a=a mod b= a-b*floor(a/b);假如我們通過遞歸得到了gcd(b,a)=b*x+a*y的x,y的值

7、，則因為gcd(a,b)=gcd(b,a mod b )=gcd(b,a);有等式gcd(a,b)=b*x+a*y代入a可以得到gcd(a,b)=b*x+(a-b*floor(a/b)*y即gcd(a,b)=a*y+b*(x-floor(a/b)*y)所以只要將gcd(a,b)=a*x+b*y中的x換為y,y換為x-floor(a/b)*y即可，同時我們有遞歸的基本情形gcd(a,0)=a*1+b*0.擴展歐幾里德算法1. EXTENDED-EUCLID(a, b)2.if b = 03.then return (a, 1, 0)4.(d,x,y) EXTENDED-EUCLID(b, a%b

8、)5.(d, x, y) (d, y, x(a/b) * y)6.return (d, x, y)擴展歐幾里德算法int ext_gcd(int a,int b,int &x,int &y)if(b=0)x=1;y=0;return a;int d=ext_gcd(b,a%b,x,y);int tx=x;x=y;y=tx-a/b*y;return d;例題二：A famous math puzzle (TOJ2219)題目描述：有n個壺，和無窮多的水每次我們只能：把其中一個壺灌滿把其中一個壺倒空把一個壺中的水倒入另一個壺中，直到一個壺為空或者另一個壺已經滿了為止給定一個體積，問能否經過若干次倒

9、水后使得最終有一個壺中只剩下升水？如果能，輸出”YES”,否則輸出”NO”例題二：A famous math puzzle (TOJ2219)Sample Input:2 4 5 62 10 65 39 2 12 4 8 3 9 10 35 14 0 0 Sample Output:YESNONOYES 例題二：A famous math puzzle (TOJ2219)要使n個水壺能倒出w體積的水，則必須符合以下兩個條件：至少有一個水壺的容量大于或等于w.假設p是n個水壺容量的最大公約數，那么w必須p的倍數例題二：A famous math puzzle (TOJ2219)假設n個水壺的容量

10、分別為C1,C2,C3 .必要性：不管執(zhí)行三種操作的那一種，壺中所含的水一定是的整數倍充分性：由歐幾里德算法擴展可知，必然存在整數A1,A2,A3.An,使得A1*C1+A2*C2+A3*C3+An*Cn=W. 如果Ai是正數，我們就用第i個壺從水源中取Ai次水；如果Ai為負數，我們就把第i個壺倒空Ai次，這樣最后必會剩下升水同余的概念兩個整數a，b，若它們除以整數m所得的余數相等，則稱a，b對于模m同余記作 a b (mod m) 讀作a與b關于模m同余。 模的相關運算(x+y)mod n=(x mod n)+(y mod n) mod n(x-y)mod n=(x mod n) - (y

11、mod n) mod nx*y mod n = (x mod n)*(y mod n) mod n乘法逆元若ax1(mod n) 則稱a對n的乘法逆元為x ,記為a-1(mod n)設b為整數，如果a對n的乘法逆元為x ，則b/a(mod n) =b*a-1 (mod n)乘法逆元并不總存在，如2x 1(mod 4).模線性方程axb(mod n)為模線性方程，x為未知數。定理一：設d=gcd(a, n)，假定對整數x和y，有d=ax+ny。如果d|b，則方程ax b(mod n)有一個解的值為x0，滿足x0=x(b/d)mod n。定理二：假設方程ax b(mod n)有解（即有d|b，其中

12、d=gcd(a, n)），x0是該方程的任意一個解，則該方程對模n恰有d個不同的解，分別為：xi=x0+i(n/d)(i = 1, 2, , d-1)。模線性方程的解法1. SOLVE(a, b, n)2. (d,x,y) EXTENDED-EUCLID(a, n)3. if (d | b)4. then x0 x(b/d)mod n5. for i 0 to d-16. print(x0 + i(n / d) mod n7.else print “無解”例題三：C Looooops (TOJ 2297)題意描述：對于以下循環(huán)語句for (variable = A; variable != B

13、; variable+= C) statement;如果給定A，B，C，k的值，statement語句會執(zhí)行多少次，假設其中所有變量都是k位無符號整數類型，（1 k 32 ）如果此循環(huán)語句不會停止，輸出” FOREVER”，否則輸出執(zhí)行次數。輸入數據以4個0結束例題三：C Looooops (TOJ 2297)Sample Input3 3 2 16 3 7 2 16 7 3 2 16 3 4 2 16 0 0 0 0 Sample Output0 2 32766 FOREVER 例題三：C Looooops (TOJ 2297)因為所有變量都是k位無符號整數類型，當語句執(zhí)行X次后，變量var

14、iable 的值變?yōu)?A+C*X)(mod 2k)所以當(A+C*X)(mod 2k)=B(mod 2k)時循環(huán)停止，化簡得C*X(B-A)(mod 2k),解模線性方程求出所有X，如果有解，輸出最小的正整數解即可，否則輸出“FOREVER”。模線性方程組例子：（孫子算經）今有物不知其數。三三數之余二；五五數之余三；七七數之余二。問物幾何？答曰：二十三。232*70+3*21+2*15(mod 105)口訣：三人同行七十稀，五樹梅花廿一枝， 七子團圓月正半，除百零五便得知。模線性方程組中國剩余定理：設自然數n1,n2,nr兩兩互素，并記N=n1n2nr，則同余方程組在模N同余的意義下有唯一解。X(a1c1+a2c2+arcr)(mod N)其中，ci=mi*(mi-1mod ni),mi=N/ni因為 Xmod ni=(a1m1m1-1+a2m2m2-1+armrmr-1) mod ni=(aimimi-1 )mod ni=aimod ni中國剩余定理/ 計算 X mod ni = ai (i = 1.k)int China(int k, int a, int n) ans = 0; N = 1 for(i = 0; i k