noip數(shù)論知識

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

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

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

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

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

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

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

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

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

10、求a－1,例：求3406寫成十進位數(shù)時的個位數(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）所以個位數(shù)是9.,思考題4:Hankson 的趣味題(noip2009),X和a0的最大公約數(shù)為a1X和b0的最小公倍數(shù)為b1給出a0,a1,b0,b

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

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

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

14、d(a,n) | b。    推論2：方程ax=b(mod n)或者對模n有d個不同的解，其中d=gcd(a,n)，或者無解。,理論,24,Extended-Euclidean 算法,對于gcd(a,b) = d，對(a, b)用歐幾里德輾轉相除會最終得到(d, 0)。此時對于把a =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 的解，那么對于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ù)，設集合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);} 該算法又叫輾轉相除法,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; },相關定理,定理1： 設d=gc

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

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

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

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

22、; 2000000000，0 < L < 2100000000。Output 輸出碰面所需要的跳躍次數(shù)，如果永遠不可能碰面則輸出一行"Impossible“Sample Input 1 2 3 4 5 Sample Output 4,解題思路,此題其實就是擴展歐幾里德算法－求解不定方程，線性同余方程?！　≡O過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ù)解。　1、先計算Gcd(a,b)，若n不能被Gcd(a,b)整除，則方程無整數(shù)解；否則，在方程兩邊同時除以Gcd(a,b)，得到新的不定

24、方程a' * x + b' * y = n'，此時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ù)論中的相關定理，可得方程

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ù)解。,解題思路,此時方程的所有解為：x=c*k1-b*t。x的最小的可

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

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

28、≡23(mod105）。,中國剩余定理,中國剩余定理（孫子定理）,求解過程,令，pi=m1*m2*...*mi-1*mi+1*…*mn, 因為mi彼此互素，因此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例：一個數(shù)被3除余1，被4除余2，被5除余4，

29、這個數(shù)最小是幾？。解：題中3、4、5三個數(shù)兩兩互質, 則〔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，因為，274>60，所以，274－60×4=34，就是所求的數(shù)。,思考題7

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

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

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

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

34、為φ(m)歐拉函數(shù)，mod m為同余關系。歐拉定理實際上是費馬小定理的推廣。比如計算7222的個位數(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。設m是正整數(shù)，a是整數(shù)，若a模m的階等于φ(m)，則稱a為模m的

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

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

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

38、的個數(shù)就是它的可逆元個數(shù)，即 φ(φ(m))個，因此當模m有原根時，它有φ(φ(m))個原根。,原根的例子,設m= 7，則φ（）等于6。設a= 2，由于2^3=8≡1(mod 7)，而3<6，所以 2 不是模 7 的一個原根。設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 的一個原根。,

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

40、ce (POI19),Description對于兩個正整數(shù)a、b，這樣定義函數(shù)d(a,b)：每次操作可以選擇一個質數(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個正整數(shù)A1,A2,...,An，對于每個i (1<=i<=n)，求最小的j(1<=j<=n)使得i≠j且d(Ai,Aj)最小。Inpu

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

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

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

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

45、gcd)就是最大公約數(shù)是gcd的倍數(shù)的數(shù)的個數(shù)，記為cnt[gcd]。從大到小枚舉gcd，然后用cnt[gcd]減去所有最大公約數(shù)是gcd的倍數(shù)的數(shù)，即為最大公約數(shù)為gcd的數(shù)的個數(shù)。復雜度為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 是一個質數(shù)

48、，或者說a和p是互質的。 首先：定義一個整數(shù)m=sqrt(p);所以：x = i * m + j (0 =0&&j=0&&i<m），計算出b*(a-m) i %p的值，每計算出一個值就去上面已經(jīng)得出的二元組里面查找有無相等的值，若有相等的值，就表示已經(jīng)找到了x，此時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的一個原根r，那么r1,r2...rphi(p)構成模p的完全剩余系。故可設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 可由離散對數(shù)求得j 由i*k=j mod p-1 可由模線性方程求得i由x= rj 求得x然后對所有x取余后排序，輸出即可。,思考題11：燈泡,有n(<=106)個燈排列成環(huán)形. 每個單位時間 燈i改變狀態(tài)當且僅當上一個時刻它下一個燈(i<n時為i

51、+1, i=n時為1)開著。給n個燈的初始狀態(tài)以及m (m<=109)求出m時間單位以后的狀態(tài).,分析,算法一: 直接模擬O(nm)算法二: 事先計算循環(huán)節(jié), 則時間復雜度和m無關, 上限是O(n2n), 但具體運行時間不好估計算法三: 第一次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)很明顯. 二分法即可. 時間復雜度為：O(nlogm),思考題12：部分和序列,n個+1，n個-1構成2n項a1,a2,a3,a4,…

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

54、為第 i 號位置，1≤ i ≤n－1。第 n 號女人與第1 號之間的位置為第 n 號位置。設第 i 號女人的丈夫的編號也為第 i 號，1≤ i ≤ n。讓 n 個男人坐到上述編號的 n 個位置上。設 ai是坐在第 i 號位置上的男人，則 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稱為二重錯排。設二重錯排的個數(shù)為Un，原問題所求的方案數(shù)就是Un (

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

57、法的計數(shù)。這相當于從1 , 2 , 2 , 3 ,3 ,4, ···,n-1, n-1, n , n , 1中取 k 個互不相鄰數(shù)的組合的計數(shù)，但首尾的１不能同時取。,一般公式,回想無重復不相鄰組合的計數(shù)：C’( n , r ) = C ( n- r + 1 , r ) ,這里所求的是：,思考題14：單色三角形,n點，無三點共線每兩點有紅線或藍線有多少個三角形的三邊同色？非單色三角形：兩個頂點連接兩