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

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

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

Fibnacci數(shù)列

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

中國剩余定理

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

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

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

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

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

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

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

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

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

設(shè)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最直接的實(shí)現(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最直接的實(shí)現(xiàn)(C++)structT{12中國剩余定理兩兩互素，求一次同余方程組

的解

只看n=2，構(gòu)造

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

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

質(zhì)數(shù)原根個(gè)數(shù)(賈怡@PKU)

大素?cái)?shù)檢驗(yàn)的Miller-Rabin概率算法多少個(gè)連續(xù)的8能整除給定的數(shù)m(網(wǎng)絡(luò)賽)

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

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

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

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

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

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

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

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

Fibnacci數(shù)列

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

中國剩余定理

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

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

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

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

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

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

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

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

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

設(shè)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最直接的實(shí)現(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最直接的實(shí)現(xiàn)(C++)structT{30中國剩余定理兩兩互素，求一次同余方程組

的解

只看n=2，構(gòu)造

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

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

質(zhì)數(shù)原根個(gè)數(shù)(賈怡@PKU)

大素?cái)?shù)檢驗(yàn)的Miller-Rabin概率算