網(wǎng)上找的一些算法數(shù)學(xué)數(shù)論

1、數(shù)論 (1)模算術(shù)運(yùn)算Xie TianDec 6th, 2009模運(yùn)算基本運(yùn)算律加法(a + b) mod P = (a mod P + b mod P) mod P減法(a - b) mod P = (a mod P - b mod P + P) mod P乘法(a * b) mod P = (a mod P) * (b mod P) mod P除法不滿足，但是有(a / b) mod P = (a mod (P * b) / b) mod P擴(kuò)展得求解Ax + By (A, B) (A, B已知, 設(shè)A B)如果B = 0，那么A =(A, B)(A, B) * x =(A, B) x =

2、 1, y = 0否則繼續(xù)遞歸，算出x和yAxBx+By=(A, B)(B, A mod B)+(A mod B)y=Ax + By = Bx + (A mod B)y演算Ax + By = Bx + (A mod B)y 展開 A mod B = A -Ax + By(A / B) * B= Bx + (A -= Bx + Ay -= Ay + B(x -(A / B) * B)y(A / B) * By(A / B) * y)(A / B) * yx = y，y = x -代碼實(shí)現(xiàn)Ax + By =(A, B)Ext(A,B,&x,&y)if(AB)returnExt(B,A,y,x);i

3、f(Bxy=0)1;0;returnA;Ret=(Ext(B,A%B,y,x);y-=x*)(A/B);returnRet;負(fù)數(shù)問題擴(kuò)展求出來的解不一定符合范圍變化成0, N - 1中的x的方法x = x mod Nx = x + Nx = x mod N解模線性方程解Ax = B (mod N) Ax - Ny = B設(shè)(A, N) = D如果B mod D != 0，那么無解令k = B / D用前法解出一組Ax - Ny =(A, N)解模線性方程那么A * kx - N * ky =(A, N) * k = B即A * kx = B (mod N)，kx是一個(gè)解下面令x為kx調(diào)整到0,

4、 N - 1的數(shù)值，即根在域內(nèi)合法解的個(gè)數(shù)為k x、x + (N / D)、x + (2N / D)、.、x + (D - 1) N / D)都要mod N乘法求(A / B) mod N如果B與N互質(zhì)，則在0, N - 1中存在唯一的關(guān)于mod N的Inv(B)，使得(A / B) mod N= (A * Inv(B) mod N部分基本運(yùn)算律Inv(B) = Inv(B mod N)Inv(A * B) = (Inv(A) * Inv(B) mod N求法：解B * Inv(B) 1 (mod N)還是要注意解出來有可能是負(fù)數(shù)例1. Counting Binary Trees(NIT Cu

5、p National Inviion Contest, Ningbo 2009)求不超過N個(gè)節(jié)點(diǎn)的不同的二叉樹的個(gè)數(shù)個(gè)數(shù)mod PN = 100000, P = 1000000000(不一定質(zhì)數(shù))N個(gè)節(jié)點(diǎn)的不同的二叉樹的個(gè)數(shù)Catalan數(shù) 遞推公式：CN = CN - 1 * (4N - 2) / (N + 1)http/onlinejudge/showProblem.do?problemCode=3183解法P不一定是質(zhì)數(shù)，意味著如果要除一個(gè)數(shù)，相應(yīng)的乘法可能不存在將P分解質(zhì)因數(shù)，找出它的所有質(zhì)因子Fi乘x，x = F1P1P2Pn* F2* . * Fn* S 將對(duì)應(yīng)的質(zhì)因數(shù)的次數(shù)加上P

6、i乘上S除x，x = F1P1P2Pn* F2* . * Fn* S 將對(duì)應(yīng)的質(zhì)因數(shù)的次數(shù)減掉Pi 此時(shí)S與P互質(zhì)，乘上Inv(S)例2. Compley Difficult(Shanghai 2009 Warmup)給定方程x3 a (mod b)保證這個(gè)方程在0, b - 1之中恰好有三個(gè)不同的根給出兩個(gè)根x1和x2，求x3b = 2000000011, b是質(zhì)數(shù)不存在提交地點(diǎn)解法聯(lián)立三個(gè)方程組 x13bk1bk2bk3= a= a= a x23 x33作差3 x1322- x3= b(k1= b(k2- k3) = (x1 - x3) (x1+ x1x3 + x3 )+ x2x3 + x

7、3 ) x23322- x3- k3) = (x2 - x3) (x2觀察 b (k1 - k3) = (x1 - x3) (x122+ x1x3+ x2x3+ x3 )+ x3 ) b (k2 - k3) = (x2 - x3) (x222首先b一定不能整除x1 - x3和x2 - x3 b是質(zhì)數(shù) 推出b一定整除x1+ x1x3 + x3 和x2+ x2x3 + x32222繼續(xù)歸納2 b t1 = x12+ x1x3 + x3 b t2 = x222+ x2x3 + x3 作差得b (t1 - t2) = (x1 - x2) (x1 + x2) + (x1 - x2) x3 即b (t1

8、- t2) = (x1 - x2) (x1 + x2 + x3)解法b (t1 - t2) = (x1 - x2) (x1 + x2 + x3)同理b不能整除x1 - x2因此b整除x1 + x2 + x3求得x3 = - x1 - x2，調(diào)整到0, N - 1即可例3. Discrete Square Roots(Hefei 2008)如果r2 x (mod N)，0 = r N，那么r是x關(guān)于mod N的一個(gè)離散平方根給出一個(gè)解r，要求求出x關(guān)于mod N的所有離散平方根N = 3)求FN mod P，P不一定為質(zhì)數(shù)N = 1000000000, P = 3) Fib(N)可能會(huì)相當(dāng)大！現(xiàn)在研究如何求aFib(N) mod PP = 1000000的方法Gx = ax mod P顯然Gx = (Gx - 1 * a) mod P也就是每一項(xiàng)只與前一項(xiàng)有關(guān)解法序列中 012. k(k + 1)(k + 2) . (k + t)其中Gk = Gk + t，序列中第一次出現(xiàn)了相同元素根據(jù)抽屜原理，k + t = P這樣G0 . Gk . Gk就形成了一個(gè)循環(huán)枚舉以找出k、t解法這樣就可以將ax中的x等價(jià)到一個(gè)較小的x探測(cè)x的大致大小 x k，x = (x mod t) +