noip數(shù)論知識(shí)

1、長(zhǎng)沙市雅禮中學(xué) 朱全民,數(shù)論,知識(shí)點(diǎn),素?cái)?shù)與合數(shù)質(zhì)因素的分解最大公約數(shù)與最小公倍數(shù)整除與同余同余方程與同余方程組歐幾里德算法、擴(kuò)展歐幾里德算法、中國(guó)剩余定理歐拉定理與費(fèi)馬小定理,思考題1：素?cái)?shù)密度,問題描述給定區(qū)間[L, R](L <= R <= 2147483647，R-L <= 1000000)，請(qǐng)計(jì)算區(qū)間中素?cái)?shù)的個(gè)數(shù)。輸入數(shù)據(jù)兩個(gè)數(shù)L和R。輸出數(shù)據(jù)一行，區(qū)間中素?cái)?shù)的個(gè)數(shù)。,梅森素?cái)?shù),

2、把形如(2p-1)形式的素?cái)?shù)稱為梅森素?cái)?shù)，p是素?cái)?shù)。[1, 231-1]之間的梅森素?cái)?shù)有：22-1, 23-1, 25-1, 27-1, 213-1, 217-1, 219-1, 231-1梅森素?cái)?shù)的一個(gè)性質(zhì)：一個(gè)正整數(shù)n的所有約數(shù)和是2的冪當(dāng)且僅當(dāng)n能夠被分解為若干個(gè)不同的梅森素?cái)?shù)之積。,思考題2:fibonacci數(shù)列,已知f1=1,f2=1fn=fn-1+fn-2給出n,如何快速求fibonacci數(shù)列的fn,分析,普通

3、的算法求Fn的時(shí)間復(fù)雜度為O(n)，當(dāng)然如果要求求出所有的Fn，這種已經(jīng)是最優(yōu)的了，但是如果只求某一個(gè)Fn，可以改進(jìn),唯一因子分解,唯一質(zhì)因子分解定理：合數(shù)a僅能以一種方式，寫成如下的乘積形式：a=p1e1p2e2…prer其中pi為素?cái)?shù)，p1<p2<…<pr，且ei為正整數(shù),,關(guān)于約數(shù)的公式,,n！的素因子分解式,整數(shù)分解方法,大整數(shù)分解現(xiàn)在任然是個(gè)世界級(jí)的難題!而對(duì)于大整數(shù)的分解有很多種算法，性能上

4、各有優(yōu)異，比如大整數(shù)分解的Fermat方法，Pollard rho方法，試除法，以及橢圓曲線法，連分?jǐn)?shù)法，二次篩選法，數(shù)域分析法等等。這里，主要講解其中兩種算法的原理和操作。,費(fèi)馬分解法,首先，對(duì)于任意的一個(gè)偶數(shù)，我們都可以提取出一個(gè)2的質(zhì)因子，如果結(jié)果仍為偶數(shù)，則可繼續(xù)該操作，直至將其化為一個(gè)奇數(shù)和2的多少次冪的乘積，那么我們可 以假定這個(gè)奇數(shù)可以被表示成2*N+1，如果這個(gè)數(shù)是合數(shù)，那么一定可以寫成N=c*d的形式，不難發(fā)現(xiàn)，式中的

5、c和d都是奇數(shù)，不妨設(shè)c>d，我 們可以令a=(c+d)/2,b=(c-d)/2，那么的可以得到N=a*a-b*b，而這正是Fermat整數(shù)分解的基礎(chǔ)；由不等式的關(guān)系，我們又可以 得到a>=sqrt(c*d)=sqrt(N)，那么，我們就可以枚舉大于N的完全平方數(shù)a*a，計(jì)算a*a-N的值，判斷計(jì)算的結(jié)果是否為一個(gè)完 全平方數(shù)，如果是，那么a，b都是N的因子，我們就可以將算法遞歸的進(jìn)行下去，知道求出N的所有質(zhì)因子。,Poll

6、ard rho算法,Pollard rho算法的原理就是通過某種方法得到兩個(gè)整數(shù)a和b，而待分解的大整數(shù)為n，計(jì)算p=gcd(a-b,n)，直到p不為1，或者a，b出現(xiàn)循環(huán)為止。然后再判斷p是否為n，如果p=n成立，那么返回n是一個(gè)質(zhì)數(shù)，否則返回p是n的一個(gè)因子，那么我們又可以遞歸的計(jì)算Pollard(p)和Pollard(n/p)，這樣，我們就可以求出n的所有質(zhì)因子。具體操作中，我們通常使用函數(shù)x2=x1*x1+c來計(jì)算逐步迭代計(jì)算

7、a和b的值，實(shí)踐中，通常取c為1，即b=a*a+1，在下一次計(jì)算中，將b的值賦給a，再次使用上式來計(jì)算新的b的值，當(dāng)a，b出現(xiàn)循環(huán)時(shí)，即可退出進(jìn)行判斷。 在實(shí)際計(jì)算中，a和b的值最終肯定一出現(xiàn)一個(gè)循環(huán)，而將這些值用光滑的曲線連接起來的話，可以近似的看成是一個(gè)ρ型的。對(duì)于Pollard rho，它可以在O(sqrt(p))的時(shí)間復(fù)雜度內(nèi)找到n的一個(gè)小因子p，可見效率還是可以的，但是對(duì)于一個(gè)因子很少、因子值很大的大整數(shù)n來說，

8、Pollard rho算法的效率仍然不是很好，那么，我們還得尋找更加的方法了。,思考題3：除法表達(dá)式,除法表達(dá)式有如下的形式：X1 / X2 / X3 / … / Xk其中Xi是正整數(shù)且Xi≤109 (1≤i≤k，k≤10 000)。除法表達(dá)式應(yīng)當(dāng)按照從左到右的順序求和，例如表達(dá)式1/2/1/2的值為1/4?？梢栽诒磉_(dá)式中嵌入括號(hào)以改變計(jì)算順序，例如表達(dá)式(1 / 2) / (1 / 2)的值為1?，F(xiàn)在給一個(gè)除法表達(dá)式E要

9、求告訴是否可以通過增加括號(hào)使表達(dá)式值為E′，E′是整數(shù)。,14,同余,設(shè)m≠0，若m∣a－b，即a－b＝km，則稱a同余于b模m，記為a、b關(guān)于模m同余的充要條件是整數(shù)a和b被同一正整數(shù)m除時(shí)，有相同的余數(shù)。,同余的性質(zhì),同余的性質(zhì),若m≥1，（a，m）＝1，則存在c使得 ca≡1（mod m）我們把c稱為是a對(duì)模m的逆，記為 a－1（mod m）或a－1可以用擴(kuò)展歐幾里德算法

10、求a－1,例：求3406寫成十進(jìn)位數(shù)時(shí)的個(gè)位數(shù).,根據(jù)題意是要求a滿足3406 ≡a（mod 10）顯然32 ≡9 ≡－1 （mod 10），34 ≡1 （mod 10），從而3404 ≡1 （mod 10），因此3406 ≡ 3404 × 32 ≡9（mod 10）所以個(gè)位數(shù)是9.,思考題4:Hankson 的趣味題(noip2009),X和a0的最大公約數(shù)為a1X和b0的最小公倍數(shù)為b1給出a0,a1,b0,b

11、1，求滿足上述條件的x的個(gè)數(shù)？,根據(jù)整數(shù)模n所得的余數(shù)，可以把整數(shù)分成n個(gè)等價(jià)類：[0],[1],…,[n-1]。包含整數(shù)的模n等價(jià)類為：[a]n={a+kn| k∈Z},模運(yùn)算,有限群：群(S, +)是一個(gè)集合S和定義在S上的二元運(yùn)算+，它滿足如下性質(zhì)：封閉性：如果a, b∈S，那么a+b ∈S。單位元：存在一個(gè)元素e，使得對(duì)于所有的a∈S都滿足e+a=a+e=a。結(jié)合律：對(duì)于任意的a, b, c都滿足(a+b)+c=a+

12、(b+c)。逆元：對(duì)每個(gè)a∈S都存在唯一的元素b∈S使得a+b=b+a=e。把b稱作a的逆元。,21,模運(yùn)算,根據(jù)模加法和模乘法定義的群：定義在集合Zn＝{0,1,2,……,n-1}上集合上的加法和乘法運(yùn)算定義為：[a]n +n [b]n = [a+b]n[a]n *n [b]n = [a*b]n,思考題5：同余方程（NOIP2012）,【問題描述】求關(guān)于x的同余方程ax≡ 1 (modb)的最小正整數(shù)解?！据斎搿枯斎?/p>

13、文件為mod.in。輸入只有一行，包含兩個(gè)正整數(shù)a, b，用一個(gè)空格隔開?！据敵觥枯敵鑫募閙od.out。輸出只有一行，包含一個(gè)正整數(shù)x0，即最小正整數(shù)解。輸入數(shù)據(jù)保證一定有解。 【數(shù)據(jù)范圍】對(duì)于40%的數(shù)據(jù)，2 ≤b≤1,000；對(duì)于60%的數(shù)據(jù)，2 ≤b≤50,000,000；對(duì)于100%的數(shù)據(jù)，2 ≤a, b≤2,000,000,000,定理：方程ax=b(mod n)對(duì)于未知量x有解，當(dāng)且僅當(dāng)gc

14、d(a,n) | b。    推論2：方程ax=b(mod n)或者對(duì)模n有d個(gè)不同的解，其中d=gcd(a,n)，或者無解。,理論,24,Extended-Euclidean 算法,對(duì)于gcd(a,b) = d，對(duì)(a, b)用歐幾里德輾轉(zhuǎn)相除會(huì)最終得到(d, 0)。此時(shí)對(duì)于把a(bǔ) =d, b = 0 代入a*x + b*y = d，顯然x = 1，y可以為任意值。我們可以用a = d, b = 0的

15、情況逆推出來任何gcd(a, b) = d 滿足a*x + b*y = d的解。如果x0，y0是b*x + (a%b)*y = d 的解，那么對(duì)于a*x + b*y = d的解呢？,25,Extended-Euclidean 算法,b*x + (a%b)*y = d →  b*x + (a - [a/b]*b)*y = a*y + b*(x - [a/b]*y)，所以a*x + b*y = d的解

16、 x1 = y0， y1= x0 - [a/b]*y0;這樣我們可以程序迭代了。,注：a,b為正整數(shù)，設(shè)集合A = {x*a+y*b|x,y是整數(shù)}，則A中最小正元素是gcd(a,b),Euclidean算法,int gcd(int a, int b) { int r; r=a%b; if(r==0) return b; else return gcd(b,r);} 該算法又叫輾轉(zhuǎn)相除法,Extended

17、-Euclidean 算法,int exGcd(int a, int b, int &x, int &y) { 　　if(b == 0) 　　{ 　　x = 1; 　　y = 0; 　　return a; 　　} 　　int r = exGcd(b, a % b, x, y); 　　int t = x; 　　x = y; 　　y = t - a / b * y; },相關(guān)定理,定理1： 設(shè)d=gc

18、d(a,n)，假定對(duì)整數(shù)x和y滿足d=ax+by(比如用擴(kuò)展Euclid算法求出的一組解)。如果d | b，則方程ax=b(mod n)有一個(gè)解x0滿足 x0=x*(b/d) mod n 。特別的設(shè)e=x0+n，方程ax=b(mod n)的最小整數(shù)解x1=e mod (n/d)，最大整數(shù)解x2=x1+(d-1)*(n/d)。 定理2：假設(shè)方程ax=b(mod n)有解，且x0是方程的任意一個(gè)解，則該方程對(duì)模n恰有d個(gè)不同的解(d=gc

19、d(a,n))，分別為：xi=x0+i*(n/d) mod n 。,兩只青蛙在網(wǎng)上相識(shí)了，它們聊得很開心，于是覺得很有必要見一面。它們很高興地發(fā)現(xiàn)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止?？墒撬鼈兂霭l(fā)之前忘記了一件很重要的事情，既沒有問清楚對(duì)方的特征，也沒有約定見面的具體位置。不過青蛙們都是很樂觀的，它們覺得只要一直朝著某個(gè)方向跳下去，總能碰到對(duì)方的。但是除非這兩只青蛙在同一時(shí)間跳到同一點(diǎn)上，不然是永遠(yuǎn)都不可能碰面的

20、。為了幫助這兩只樂觀的青蛙，你被要求寫一個(gè)程序來判斷這兩只青蛙是否能夠碰面，會(huì)在什么時(shí)候碰面。,思考題6：青蛙的約會(huì)(POJ 1061),我們把這兩只青蛙分別叫做青蛙A和青蛙B，并且規(guī)定緯度線上東經(jīng)0度處為原點(diǎn)，由東往西為正方向，單位長(zhǎng)度1米，這樣我們就得到了一條首尾相接的數(shù)軸。設(shè)青蛙A的出發(fā)點(diǎn)坐標(biāo)是x，青蛙B的出發(fā)點(diǎn)坐標(biāo)是y。青蛙A一次能跳m米，青蛙B一次能跳n米，兩只青蛙跳一次所花費(fèi)的時(shí)間相同。緯度線總長(zhǎng)L米?，F(xiàn)在要你求出它們跳了幾

21、次以后才會(huì)碰面。輸入只包括一行5個(gè)整數(shù)x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。輸出碰面所需要的跳躍次數(shù)，如果永遠(yuǎn)不可能碰面則輸出一行"Impossible",Input 輸入只包括一行5個(gè)整數(shù)x，y，m，n，L，其中x≠y < 2000000000，0 < m、n <

22、; 2000000000，0 < L < 2100000000。Output 輸出碰面所需要的跳躍次數(shù)，如果永遠(yuǎn)不可能碰面則輸出一行"Impossible“Sample Input 1 2 3 4 5 Sample Output 4,解題思路,此題其實(shí)就是擴(kuò)展歐幾里德算法－求解不定方程，線性同余方程。　　設(shè)過s步后兩青蛙相遇，則必滿足以下等式：　　　　(x+m*s)-(y+n*s)=

23、k*l(k=0,1,2....)　　稍微變一下形得：　　　　(n-m)*s+k*l=x-y    令n-m=a,k=b,x-y=c,即　　　　a*s+b*l=c只要上式存在整數(shù)解，則兩青蛙能相遇，否則不能。,解題思路,求a * x + b * y = n的整數(shù)解?！?、先計(jì)算Gcd(a,b)，若n不能被Gcd(a,b)整除，則方程無整數(shù)解；否則，在方程兩邊同時(shí)除以Gcd(a,b)，得到新的不定

24、方程a' * x + b' * y = n'，此時(shí)Gcd(a',b')=1;   2、利用上面所說的歐幾里德算法求出方程a' * x + b' * y = 1的一組整數(shù)解x0,y0，則n' * x0,n' * y0是方程a' * x + b' * y = n'的一組整數(shù)解；　3、根據(jù)數(shù)論中的相關(guān)定理，可得方程

25、a' * x + b' * y = n'的所有整數(shù)解為：        x = n' * x0 + b' * t y = n' * y0 - a' * t (t為整數(shù))上面的解也就是a * x + b * y = n 的全部整數(shù)解。,解題思路,此時(shí)方程的所有解為：x=c*k1-b*t。x的最小的可

26、能值是0令x=0，可求出當(dāng)x最小時(shí)的t的取值，但由于x=0是可能的最小取值，實(shí)際上可能x根本取不到0，那么由計(jì)算機(jī)的取整除法可知：由 t=c*k1/b算出的t，代回x=c*k1-b*t中。求出的x可能會(huì)小于0，此時(shí)令t=t+1，求出的x必大于0；如果代回后x仍是大于等于0的，那么不需要再做修正。,中國(guó)剩余定理,若有一些兩兩互質(zhì)的整數(shù)m1, m2,… mn，則對(duì)任意的整數(shù)：a1,a2,...an，以下聯(lián)立同余方程組對(duì)模數(shù)m1, m2,

27、… mn 有公解：,公元5－6世紀(jì)前后的《孫子算經(jīng)》中有“物不知數(shù)”問題：“今有物不知其數(shù)，三三數(shù)之余二 ，五五數(shù)之余三 ，七七數(shù)之余二，問物幾何？”答為“23”。也就是求同余式組x≡2 （mod3），x≡3 （mod5 ），x≡2 （mod7）的正整數(shù)解。明朝程大位用歌謠給出了該題的解法：“三人同行七十稀，五樹梅花廿一枝，七子團(tuán)圓月正半，除百零五便得知。”即解為 x≡2×70＋3×21＋2×15≡233

28、≡23(mod105）。,中國(guó)剩余定理,中國(guó)剩余定理（孫子定理）,求解過程,令，pi=m1*m2*...*mi-1*mi+1*…*mn, 因?yàn)閙i彼此互素，因此pi與mi彼此互素,但被mj(i)整除。令，m=m1*m2*...*mi-1*mi*mi+1*…*mn令，bi=ki*pi使得，ki為整數(shù)，使得bi mod mi=1則，x=（b1*a1+b2*a2+…+bn*an）mod m例：一個(gè)數(shù)被3除余1，被4除余2，被5除余4，

29、這個(gè)數(shù)最小是幾？。解：題中3、4、5三個(gè)數(shù)兩兩互質(zhì), 則〔4，5〕=20；〔3，5〕=15；〔3，4〕=12；〔3，4，5〕=60。為了使20被3除余1，用20×2=40；使15被4除余1，用15×3=45；使12被5除余1，用12×3=36。然后，40×1+45×2+36×4=274，因?yàn)椋?74>60，所以，274－60×4=34，就是所求的數(shù)。,思考題7

30、：荒島野人(NOI2002),克里特島以野人群居而著稱。島上有排列成環(huán)行的M個(gè)山洞，順時(shí)針編號(hào)為1,2,…, M島上住著N個(gè)野人一開始依次住在山洞C1,C2,…, CN中以后每年，第i個(gè)野人會(huì)沿順時(shí)針向前走Pi個(gè)洞住下來每個(gè)野人i有一個(gè)壽命值Li，即生存的年數(shù)。至少有多少個(gè)山洞才能讓任何兩個(gè)野人在有生之年都不可能處在同一個(gè)山洞中,【輸入文件】第1行為一個(gè)整數(shù)N(1<=N<=15)，即野人的數(shù)目。第2行到第N

31、+1每行為三個(gè)整數(shù)Ci, Pi, Li (1<=Ci,Pi<=100, 0<=Li<=106 )，表示每個(gè)野人所住的初始洞穴編號(hào)，每年走過的洞穴數(shù)及壽命值。 【輸出文件】?jī)H包含一個(gè)數(shù)M，即最少可能的山洞數(shù)。輸入數(shù)據(jù)保證有解，且M不大于106。,樣例,下面四幅圖描述了一個(gè)有6個(gè)山洞，住有三個(gè)野人的島上前四年的情況。三個(gè)野人初始的洞穴編號(hào)依次為1，2，3；每年要走過的洞穴數(shù)依次為3，7，2；壽命值依

32、次為4，3，1。,解題思路,用Ci, Pi, Li (1<=Ci,Pi<=100, 0<=Li<=106 )，表示每個(gè)野人所住的初始洞穴編號(hào)，每年走過的洞穴數(shù)及壽命值，則有如果兩個(gè)野人相遇, 則 c[i]+p[i]*x==c[j]+p[j]*x(mod m)所以轉(zhuǎn)化為（p[i]-p[j])*x==(c[j]-c[i])(mod m)利用擴(kuò)展歐幾里得，可以判斷模線性方程是否有解。,歐拉函數(shù),Euler函數(shù)

33、 ：設(shè)m是正整數(shù)，1，2，…，m中與m互素的數(shù)的個(gè)數(shù)。此函數(shù)以其首名研究者歐拉命名，它又稱為φ函數(shù)、歐拉商數(shù)等。例如，因?yàn)?,3,5,7均和8互質(zhì)。 定理：,費(fèi)馬小定理,假如a是一個(gè)整數(shù)，p是一個(gè)素?cái)?shù)，那么 ap ≡a (mod p)。如果a不是p的倍數(shù)，這個(gè)定理也可以寫成ap-1 ≡1 (mod p)。----這個(gè)更加常用,歐拉定理,若m,a為正整數(shù)，且m,a互素，(gcd(a,m) = 1)，則aφ(m)≡1，其中

34、為φ(m)歐拉函數(shù)，mod m為同余關(guān)系。歐拉定理實(shí)際上是費(fèi)馬小定理的推廣。比如計(jì)算7222的個(gè)位數(shù)，實(shí)際是求7222 mod 10。 7和10互素，且φ(10)=4,。由歐拉定理知74≡1 (mod 10)。所以 7222 =74*55+2=(74)55 *72 ≡155 *72 ≡49 ≡9 (mod 10),原根,原根的定義：原根Primitive Root。設(shè)m是正整數(shù)，a是整數(shù)，若a模m的階等于φ(m)，則稱a為模m的

35、一個(gè)原根。（其中φ(m)表示m的歐拉函數(shù)）假設(shè)一個(gè)數(shù)g對(duì)于P來說是原根，那么gi mod P的結(jié)果兩兩不同,且有 1<g<P, 0<i<P,那么g可以稱為是P的一個(gè)原根,歸根到底就是gP-1 = 1 (mod P)當(dāng)且僅當(dāng)指數(shù)為P-1的時(shí)候成立.(這里P是素?cái)?shù)).簡(jiǎn)單來說， gi mod p ≠ gj mod p （p為素?cái)?shù)）其中i≠j且i, j介於1至(p-1)之間則g為p的原根。求原根目前的做法只能

36、是從2開始枚舉，然后暴力判斷 gP-1 = 1 (mod P)是否當(dāng)且當(dāng)指數(shù)為P-1的時(shí)候成立而由于原根一般都不大，所以可以暴力得到.,原根的性質(zhì),1）可以證明，如果正整數(shù)(a,m) = 1和正整數(shù) d 滿足a^d≡1(mod 7)，則 d 整除 φ(m)。因此 Ordm(a)整除φ(m)。在例子中，當(dāng)a= 3時(shí)，我們僅需要驗(yàn)證 3 的 1 、2、3 和 6 次方模 7 的余數(shù)即可。2）記δ = Ordm(a)，則a^1，……a^(

37、δ-1)模 m 兩兩不同余。因此當(dāng)a是模m的原根時(shí)，a^0,a^1，……a^(δ-1)構(gòu)成模 m 的簡(jiǎn)化剩余系。3）模m有原根的充要條件是m= 1,2,4,p,2p,p^n，其中p是奇質(zhì)數(shù)，n是任意正整數(shù)。4）對(duì)正整數(shù)(a,m) = 1，如果 a 是模 m 的原根，那么 a 是整數(shù)模n乘法群（即加法群 Z/mZ的可逆元，也就是所有與 m 互素的正整數(shù)構(gòu)成的等價(jià)類構(gòu)成的乘法群）Zn的一個(gè)生成元。由于Zn有 φ(m)個(gè)元素，而它的生成元

38、的個(gè)數(shù)就是它的可逆元個(gè)數(shù)，即 φ(φ(m))個(gè)，因此當(dāng)模m有原根時(shí)，它有φ(φ(m))個(gè)原根。,原根的例子,設(shè)m= 7，則φ（）等于6。設(shè)a= 2，由于2^3=8≡1(mod 7)，而3<6，所以 2 不是模 7 的一個(gè)原根。設(shè)a= 3，由于3^1≡3(mod 7)，3^2≡2(mod 7)，3^3≡6(mod 7)，3^4≡4(mod 7)，3^5≡5(mod 7)，3^6≡1(mod 7)，所以 3 是模 7 的一個(gè)原根。,

39、Miller-Rabin測(cè)試,對(duì)于奇數(shù)n, 記n=2r*s+1, 其中s為奇數(shù)隨機(jī)選a(1<=a<=n-1), n通過測(cè)試的條件是as≡1(mod n), 或者存在0<=j<=r-1使得a2^j*s≡-1(mod n)素?cái)?shù)對(duì)于所有a通過測(cè)試, 合數(shù)通過測(cè)試的概率不超過1/4只測(cè)試a=2, 3, 5, 7, 則2.5*1013以內(nèi)唯一一個(gè)可以通過所有測(cè)試的數(shù)為3215031751,思考題8： Distan

40、ce (POI19),Description對(duì)于兩個(gè)正整數(shù)a、b，這樣定義函數(shù)d(a,b)：每次操作可以選擇一個(gè)質(zhì)數(shù)p，將a變成a*p或a/p，如果選擇變成a/p就要保證p是a的約數(shù)，d(a,b)表示將a變成b所需的最少操作次數(shù)。例如d(69,42)=3。現(xiàn)在給出n個(gè)正整數(shù)A1,A2,...,An，對(duì)于每個(gè)i (1<=i<=n)，求最小的j(1<=j<=n)使得i≠j且d(Ai,Aj)最小。Inpu

41、t第一行一個(gè)正整數(shù)n (2<=n<=100,000)。第二行n個(gè)正整數(shù)A1,A2,...,An (Ai<=1,000,000)。Output輸出n行，依次表示答案。,分析,題意：給定n個(gè)數(shù)，對(duì)于每個(gè)數(shù)求離其距離最小的數(shù)的標(biāo)號(hào)，每?jī)蓚€(gè)數(shù)的距離是指a*b/gcd(a,b)的質(zhì)因數(shù)的個(gè)數(shù)，相同質(zhì)因數(shù)是算多次的，比如說4就是2，24就是4。很顯然看數(shù)據(jù)范圍是O(nlogn)的，那么考慮一下有哪些算法是這個(gè)時(shí)間復(fù)雜度

42、一下的就可以了。,分析,首先O(nlogn)處理出每個(gè)數(shù)的質(zhì)因數(shù)個(gè)數(shù)。然后枚舉gcd，處理出這個(gè)數(shù)的所有倍數(shù)。那么暫且將這個(gè)數(shù)作為gcd來做（如果它不是這兩個(gè)數(shù)的gcd，肯定不會(huì)不答案優(yōu)的）。在其倍數(shù)中選出質(zhì)因數(shù)個(gè)數(shù)最小的，那么對(duì)于其每個(gè)倍數(shù)，答案就是其質(zhì)因數(shù)的個(gè)數(shù)+最小的那個(gè)的質(zhì)因數(shù)個(gè)數(shù)-2*gcd的質(zhì)因數(shù)的個(gè)數(shù)。當(dāng)然得注意一下自己不能和自己搞的，用其更新答案就可以了。,思考題9：能量采集（ NOI2010 ）,題意：平面上有n

43、*m個(gè)整點(diǎn)，坐標(biāo)為(x, y)，1≤x≤n，1≤y≤m。若(x, y)與(0,0)的連線上有k個(gè)整點(diǎn)，則(x, y)損失2k+1。問總共的損失是多少。數(shù)據(jù)范圍對(duì)于10%的數(shù)據(jù)：1 ≤ n, m ≤ 10；對(duì)于50%的數(shù)據(jù)：1 ≤ n, m ≤ 100；對(duì)于80%的數(shù)據(jù)：1 ≤ n, m ≤ 1000；對(duì)于90%的數(shù)據(jù)：1 ≤ n, m ≤ 10,000；對(duì)于100%的數(shù)據(jù)：1 ≤ n, m ≤ 100,000。,分析,依次枚

44、舉所有可能的坐標(biāo)(x, y)，計(jì)算(x, y)與(0, 0)的連續(xù)上有多少個(gè)整點(diǎn)即可。設(shè)g為x和y的最大公約數(shù)，不難證明，所以(x, y)與(0, 0)的連線上的點(diǎn)的坐標(biāo)都是(kx/g, ky/g)的形式，其中k是整數(shù)，所以不難得出連線上的整點(diǎn)個(gè)數(shù)為g-1個(gè)。選手只要枚舉x, y，使用歐幾里得算法計(jì)算x和y的最大公約數(shù)g，即可計(jì)算出答案，該算法的復(fù)雜度為O(n2logn)，可以得到80%的分?jǐn)?shù)。,分析,枚舉gcd，(n/gcd)*(m/

45、gcd)就是最大公約數(shù)是gcd的倍數(shù)的數(shù)的個(gè)數(shù)，記為cnt[gcd]。從大到小枚舉gcd，然后用cnt[gcd]減去所有最大公約數(shù)是gcd的倍數(shù)的數(shù)，即為最大公約數(shù)為gcd的數(shù)的個(gè)數(shù)。復(fù)雜度為1/n+2/n+..n/n=nlogn。,思考題10： Discrete Logging (poj2417),DescriptionGiven a prime P, 2 <= P < 231, an integer B, 2 &

46、lt;= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that BL == N (mod P)InputRead several lines of input, each containing P,B,N se

47、parated by a space.OutputFor each line print the logarithm on a separate line. If there are several, print the smallest; if there is none, print "no solution".,baby_step,giant_step算法,解 ax = b (mod p)，p 是一個(gè)質(zhì)數(shù)

48、，或者說a和p是互質(zhì)的。 首先：定義一個(gè)整數(shù)m=sqrt(p);所以：x = i * m + j (0 =0&&j=0&&i<m），計(jì)算出b*(a-m) i %p的值，每計(jì)算出一個(gè)值就去上面已經(jīng)得出的二元組里面查找有無相等的值，若有相等的值，就表示已經(jīng)找到了x，此時(shí)x=i*m+j。若枚舉完i后，無相等值就表示無x成立。,思考題10： Discrete Roots（ sgu261）,http://

49、acm.sgu.ru/problem.php?contest=0&problem=261題意：給定數(shù)P,K,A，求x，使得x^K=A mod P。數(shù)據(jù)范圍：2 <= P <= 10^9 2 <= K <= 1000000 <= A < P所有的解在[0..p-1]范圍內(nèi),分析,我們可以求出p的一個(gè)原根r，那么r1,r2...rphi(p)構(gòu)成模p的完全剩余系。故可設(shè)x=r

50、i ，a=rj，由 xk=a (mod p),那么等式化成 r (i*k)=rj (mod p)那么由定理可得 i*k=j (mod p-1)由rj =a mod p 可由離散對(duì)數(shù)求得j 由i*k=j mod p-1 可由模線性方程求得i由x= rj 求得x然后對(duì)所有x取余后排序，輸出即可。,思考題11：燈泡,有n(<=106)個(gè)燈排列成環(huán)形. 每個(gè)單位時(shí)間 燈i改變狀態(tài)當(dāng)且僅當(dāng)上一個(gè)時(shí)刻它下一個(gè)燈(i<n時(shí)為i

51、+1, i=n時(shí)為1)開著。給n個(gè)燈的初始狀態(tài)以及m (m<=109)求出m時(shí)間單位以后的狀態(tài).,分析,算法一: 直接模擬O(nm)算法二: 事先計(jì)算循環(huán)節(jié), 則時(shí)間復(fù)雜度和m無關(guān), 上限是O(n2n), 但具體運(yùn)行時(shí)間不好估計(jì)算法三: 第一次a[1,i]= a[0,i]xor a[0,i+1], 第二次a[2,i]= a[1,i]xor a[1,i+1] = (a[0,i]xor a[0,i+1]) or (

52、a[0,i+1] or a[0,i+2]) = a[0,i]xor a[0,i+2], 第四次a[4,i]=a[2,i]xor a[2,i+2] = (a[0,i]xor a[0,i+2]) xor (a[0,i+2] xor a[0,i+4])=a[0,i] xor a[0,i+4]至此,規(guī)律已經(jīng)很明顯. 二分法即可. 時(shí)間復(fù)雜度為：O(nlogm),思考題12：部分和序列,n個(gè)+1，n個(gè)-1構(gòu)成2n項(xiàng)a1,a2,a3,a4,…

53、,a2n對(duì)任意 的k,k=1,2,3,...2n求其部分和滿足a1+a2+... +ak >=0的數(shù)列個(gè)數(shù)。,思考題13：圓桌問題,設(shè) n 對(duì)夫妻圍圓桌而坐，男女相間，每個(gè)男人都不和他的妻子相鄰，有多少種可能的方案？,分析,不妨設(shè) n 個(gè)女人先圍成一圈，方案數(shù)為( n－1 )! 。對(duì)任一這樣的給定方案，順時(shí)針給每個(gè)女人以編號(hào)1 , 2 , ··· , n。設(shè)第i號(hào)與第 i + 1號(hào)女人之間的位置

54、為第 i 號(hào)位置，1≤ i ≤n－1。第 n 號(hào)女人與第1 號(hào)之間的位置為第 n 號(hào)位置。設(shè)第 i 號(hào)女人的丈夫的編號(hào)也為第 i 號(hào)，1≤ i ≤ n。讓 n 個(gè)男人坐到上述編號(hào)的 n 個(gè)位置上。設(shè) ai是坐在第 i 號(hào)位置上的男人，則 ai ≠ i ，i + 1，１≤ i ≤n－1；an≠n，1。,分析,這樣的限制也即要求在下面3行n列的排列中每列中都無相同元素。,１?。病。场?···　 ·

55、··　n－１　n２　３?。础?···　 ···　n　　　1 a1　 a2 a3 ··· ··· an－1 an,滿足這樣的限制的排列 a1a2 ···an稱為二重錯(cuò)排。設(shè)二重錯(cuò)排的個(gè)數(shù)為Un，原問題所求的方案數(shù)就是Un (

56、 n－1)！。,分析,設(shè)Ai為 ai = i或 i+ 1 (1≤ i ≤n-1 )，an = n或1的排列 a1 a2 ··· an的集合。則｜Ai｜= 2 (n-1)! ，關(guān)鍵是計(jì)算 ∑ |∩Ai|,,i∈I,I ∈￠( n , k),也就是從( 1 , 2 ) ( 2 , 3 ) ··· ( n-1, n ) ( n , 1)這n對(duì)數(shù)的k 對(duì)中各取一數(shù)，且互不相同的取

57、法的計(jì)數(shù)。這相當(dāng)于從1 , 2 , 2 , 3 ,3 ,4, ···,n-1, n-1, n , n , 1中取 k 個(gè)互不相鄰數(shù)的組合的計(jì)數(shù)，但首尾的１不能同時(shí)取。,一般公式,回想無重復(fù)不相鄰組合的計(jì)數(shù)：C’( n , r ) = C ( n- r + 1 , r ) ,這里所求的是：,思考題14：?jiǎn)紊切?n點(diǎn)，無三點(diǎn)共線每?jī)牲c(diǎn)有紅線或藍(lán)線有多少個(gè)三角形的三邊同色？非單色三角形：兩個(gè)頂點(diǎn)連接兩