算法ACM-ICPC中的數(shù)學課件

ACM/ICPC中的數(shù)學ACM/ICPC中的數(shù)學1數(shù)論組合數(shù)學（計數(shù)問題）博弈概率二、三分，積分數(shù)論2預備代數(shù)知識代數(shù)結構半群群、子群、Lagrange定理環(huán)、交換幺環(huán)預備代數(shù)知識代數(shù)結構3快速冪乘半群上元素冪的lgN算法計算a^b%c

細節(jié)：在32位機器上如何計算64位整數(shù)相乘對64位整數(shù)取模？矩陣快速冪乘

Fibnacci數(shù)列

題目：字符串接力計數(shù)快速冪乘半群上元素冪的lgN算法4初等數(shù)論在ICPC中的幾點Euclid輾轉相除法

中國剩余定理

Euler定理初等數(shù)論在ICPC中的幾點5一些記號和結論整除：若a=b*q,b!=0,稱b整除a,記作b|a同余：若c|(b-a),稱a,b對c同余，記作a=b(modc)除法定理：給定a,b兩個整數(shù)，b>0,則存在兩個唯一的整數(shù)q,r,使得a=b*q+r,0<=r<b成立唯一分解定理（標準分解）：任一自然數(shù)n>0,均可唯一表示為素數(shù)之積:

一些記號和結論6最大公約數(shù)最小公倍數(shù)模m的剩余類環(huán)

縮系最大公約數(shù)7N個數(shù)的最大公約數(shù)

給定N個數(shù)，求它們的最大公約數(shù)N個數(shù)的最大公約數(shù)

給定N個數(shù)，求它們的最大公約數(shù)8Euclid輾轉相除法給定a,b不全為0，求gcd(a,b)結論:復雜度O(lg(b))，可參看《算法導論》Euclid輾轉相除法給定a,b不全為0，求gcd(a,b)9青蛙的約會（浙江OI）：

長Ｌ的緯度線上，兩只青蛙同時往西跳，規(guī)定從東往西為正方向建立坐標軸，兩只青蛙的坐標分別為x和y，每一跳分別跳m米和n米，二只青蛙每一跳花的時間相同。問兩只青蛙能否相遇？青蛙的約會（浙江OI）：

長Ｌ的緯度線上，兩只青蛙同時往西跳10拓展Euclid算法給定a,b不全為0，求d,x,y使得

d=gcd(a,b)=a*x+b*y

注：不唯一，調(diào)整下就可以作為另一組解在Euclid算法上作一點手腳:

設a>b>0,a=b*q+c(除法定理)

若d=x’*b+y’*c

則d=y’*a+(x’–q)*b拓展Euclid算法給定a,b不全為0，求d,x,y使得

d11exEuc最直接的實現(xiàn)(C++)structT{ intd,x,y;};TexEuc(inta,intb){ if(b==0)returnT(a,0,0); Ttmp=exEuc(b,a%b); returnT(tmp.d,tmp.y,tmp.x-(a/b)*tmp.y);}//自己證明求得的x,y是否小于max(a,b)exEuc最直接的實現(xiàn)(C++)structT{12中國剩余定理兩兩互素，求一次同余方程組

的解

只看n=2，構造

POJ2891中國剩余定理兩兩互素，求一次同余方程組

13質數(shù)表質數(shù)表：保存素因子，標準分解平方往外篩法(O(n*lglg(n)),復雜度未驗證)線性篩法(O(n))質數(shù)表質數(shù)表：保存素因子，標準分解14Euler函數(shù)小于n且與n互素的數(shù)的個數(shù)n為素數(shù)或素數(shù)冪時的若設n的標準分解為Euler函數(shù)小于n且與n互素的數(shù)15Euler定理若(a,n)=1,則Fermat小定理Euler定理若(a,n)=1,則16多少個連續(xù)的8能整除給定的數(shù)m(網(wǎng)絡賽)

質數(shù)原根個數(shù)(賈怡@PKU)

大素數(shù)檢驗的Miller-Rabin概率算法多少個連續(xù)的8能整除給定的數(shù)m(網(wǎng)絡賽)

17單調(diào)函數(shù)（數(shù)列）二分求解

如有序數(shù)列的查找

方程的數(shù)值計算（二分法求數(shù)值解）

次數(shù)(復雜度)：離散的：lg(n);方程的單峰函數(shù):三分法求峰值：dp優(yōu)化等數(shù)值積分基本概念

Gauss型外推法，Romberg數(shù)值積分單調(diào)函數(shù)（數(shù)列）二分求解

如有序數(shù)列的查找

方程的數(shù)值計算（18ACM/ICPC中的數(shù)學ACM/ICPC中的數(shù)學19數(shù)論組合數(shù)學（計數(shù)問題）博弈概率二、三分，積分數(shù)論20預備代數(shù)知識代數(shù)結構半群群、子群、Lagrange定理環(huán)、交換幺環(huán)預備代數(shù)知識代數(shù)結構21快速冪乘半群上元素冪的lgN算法計算a^b%c

細節(jié)：在32位機器上如何計算64位整數(shù)相乘對64位整數(shù)取模？矩陣快速冪乘

Fibnacci數(shù)列

題目：字符串接力計數(shù)快速冪乘半群上元素冪的lgN算法22初等數(shù)論在ICPC中的幾點Euclid輾轉相除法

中國剩余定理

Euler定理初等數(shù)論在ICPC中的幾點23一些記號和結論整除：若a=b*q,b!=0,稱b整除a,記作b|a同余：若c|(b-a),稱a,b對c同余，記作a=b(modc)除法定理：給定a,b兩個整數(shù)，b>0,則存在兩個唯一的整數(shù)q,r,使得a=b*q+r,0<=r<b成立唯一分解定理（標準分解）：任一自然數(shù)n>0,均可唯一表示為素數(shù)之積:

一些記號和結論24最大公約數(shù)最小公倍數(shù)模m的剩余類環(huán)

縮系最大公約數(shù)25N個數(shù)的最大公約數(shù)

給定N個數(shù)，求它們的最大公約數(shù)N個數(shù)的最大公約數(shù)

給定N個數(shù)，求它們的最大公約數(shù)26Euclid輾轉相除法給定a,b不全為0，求gcd(a,b)結論:復雜度O(lg(b))，可參看《算法導論》Euclid輾轉相除法給定a,b不全為0，求gcd(a,b)27青蛙的約會（浙江OI）：

長Ｌ的緯度線上，兩只青蛙同時往西跳，規(guī)定從東往西為正方向建立坐標軸，兩只青蛙的坐標分別為x和y，每一跳分別跳m米和n米，二只青蛙每一跳花的時間相同。問兩只青蛙能否相遇？青蛙的約會（浙江OI）：

長Ｌ的緯度線上，兩只青蛙同時往西跳28拓展Euclid算法給定a,b不全為0，求d,x,y使得

d=gcd(a,b)=a*x+b*y

注：不唯一，調(diào)整下就可以作為另一組解在Euclid算法上作一點手腳:

設a>b>0,a=b*q+c(除法定理)

若d=x’*b+y’*c

則d=y’*a+(x’–q)*b拓展Euclid算法給定a,b不全為0，求d,x,y使得

d29exEuc最直接的實現(xiàn)(C++)structT{ intd,x,y;};TexEuc(inta,intb){ if(b==0)returnT(a,0,0); Ttmp=exEuc(b,a%b); returnT(tmp.d,tmp.y,tmp.x-(a/b)*tmp.y);}//自己證明求得的x,y是否小于max(a,b)exEuc最直接的實現(xiàn)(C++)structT{30中國剩余定理兩兩互素，求一次同余方程組

的解

只看n=2，構造

POJ2891中國剩余定理兩兩互素，求一次同余方程組

31質數(shù)表質數(shù)表：保存素因子，標準分解平方往外篩法(O(n*lglg(n)),復雜度未驗證)線性篩法(O(n))質數(shù)表質數(shù)表：保存素因子，標準分解32Euler函數(shù)小于n且與n互素的數(shù)的個數(shù)n為素數(shù)或素數(shù)冪時的若設n的標準分解為Euler函數(shù)小于n且與n互素的數(shù)33Euler定理若(a,n)=1,則Fermat小定理Euler定理若(a,n)=1,則34多少個連續(xù)的8能整除給定的數(shù)m(網(wǎng)絡賽)

質數(shù)原根個數(shù)(賈怡@PKU)

大素數(shù)檢驗的Miller-Rabin概率算