oi中的數(shù)論

1、OI中的初等數(shù)論入門,進(jìn)位計(jì)數(shù)制,進(jìn)制表示 表示b進(jìn)制下的n位數(shù)。,,b進(jìn)制向十進(jìn)制轉(zhuǎn)換：乘以基數(shù)并展開：,十進(jìn)制向b進(jìn)制轉(zhuǎn)換：整數(shù)部分除以基數(shù)并倒取余數(shù)。小數(shù)部分乘以基數(shù)，并順取整數(shù)部分。,一個(gè)天平，砝碼分別為1g、3g、9g、27g、…6561g…，每個(gè)砝碼只有一個(gè)，要稱重的物品放在天平的左側(cè)，而砝碼允許放在天平的左右兩側(cè)。已知一個(gè)物品的質(zhì)量N，問(wèn)如何稱重？數(shù)據(jù)規(guī)模：N≤108,天平I,分析：就是將N

2、轉(zhuǎn)換成三進(jìn)制后，將三進(jìn)制中的0、1、2三個(gè)狀態(tài)轉(zhuǎn)換成 0、1 、-1 ，具體的說(shuō)，就是0和1不變，2變成-1后，其高一位加1。,一個(gè)天平，砝碼分別為1g、3g、9g、27g、… 6561g…，每個(gè)砝碼只有一個(gè)，要稱重的物品放在天平的左側(cè)，而砝碼只允許放在天平的右側(cè)。將由這個(gè)系統(tǒng)可以稱出來(lái)的重量按從小到大的順序進(jìn)行排列，得到下列序列：1,3,4,9,10,...。問(wèn)其中的第K個(gè)重量是多少？數(shù)據(jù)規(guī)模：K≤105,天平II,分析：這就是N

3、OIP2006PJ《序列》中p=3時(shí)的簡(jiǎn)化版將K轉(zhuǎn)換成二進(jìn)制并按三(p=3)進(jìn)制展開。,一天，CC買了N個(gè)容量可以認(rèn)為是無(wú)限大的瓶子，開始時(shí)每個(gè)瓶子里有1升水。接著CC他決定保留不超過(guò)K個(gè)瓶子。每次他選擇兩個(gè)當(dāng)前含水量相同的瓶子，合并并丟棄一個(gè)空瓶（不能丟棄有水的瓶子）。顯然在某些情況下CC無(wú)法達(dá)到目標(biāo)。此時(shí)CC會(huì)重新買一些新的瓶子（新瓶子容量無(wú)限，開始時(shí)有1升水），以達(dá)到目標(biāo)。問(wèn)最少需要買多少新瓶子才能達(dá)到目標(biāo)呢？數(shù)據(jù)規(guī)模：N≤1

4、09,K≤1000,倒水,分析：根據(jù)題意，保留的瓶子的水容量一定為2的方冪，就是求N的二進(jìn)制形式中，從高位到低位保留K位1，所需要補(bǔ)充的最小差值。例如N=27=(11011)2,k=3時(shí),數(shù)字分離及回文數(shù),數(shù)字分離用于統(tǒng)計(jì)整數(shù)數(shù)碼、位數(shù)、逆序等 while (n>0){ // n%10 就是n的每一位數(shù)字 n/=10; },int cont(int n){//統(tǒng)計(jì)n的位數(shù) int s=

5、0; while (n>0){ s++; n/=10; } return s;}int sum(int n){//統(tǒng)計(jì)n的數(shù)字和 int s=0; while (n>0){ s+=n%10; n/=10; } return s;},int rev(int n){//計(jì)算n的逆序數(shù) int s=0; while

6、 (n>0){ s=s*10+n%10; n/=10; } return s;}bool pal(int n){//判斷n是否為回文數(shù) int s=0,m=n; while (n>0){ s=s*10+n%10; n/=10; } return s==m;},bool palb(int n,int b){ //判斷n在b進(jìn)制下是

7、否為回文數(shù) int s=0,m=n; while (n>0){ s=s*b + n%b; n/=b; } return s==m;}注意：循環(huán)內(nèi)的乘b加，表示將n按b進(jìn)制下的逆序展開。,輸入一個(gè)正整數(shù)N，求從1到N中十進(jìn)制、二進(jìn)制和八進(jìn)制均為回文數(shù)的數(shù)字個(gè)數(shù)。注意：一位數(shù)也是回文數(shù)。數(shù)據(jù)規(guī)模：N≤1000000。,進(jìn)制回文數(shù),給定一個(gè)進(jìn)制B(2≤B≤20,由十進(jìn)制表示)和

8、N，輸出所有的大于等于1小于等于N（十進(jìn)制下）且它的平方用B進(jìn)制表示時(shí)是回文數(shù)的數(shù)。用’A’,’B’……表示10，11等等。 數(shù)據(jù)規(guī)模：N≤100000,回文平方數(shù),求第i個(gè)回文數(shù)數(shù)據(jù)規(guī)模：i≤109分析：注意回文數(shù)的特點(diǎn)：1~9為最初的9個(gè)回文數(shù)，11~99為其次的9個(gè)回文數(shù)，為1~9進(jìn)行翻轉(zhuǎn)而得到；依此類推，可以得到所有的回文數(shù)。,第i個(gè)回文數(shù),整除,設(shè) a,b為整數(shù)，a≠0. 若有一整數(shù)q, 使得 b = aq, 則稱 a

9、是b的因數(shù)，b為是a的倍數(shù)；并稱a整除b, 記為a|b；若a不能整除b，則記為a b。,基本性質(zhì),①若c | b，b | a，則c | a ②若c | a，d | b，則cd | ab③若c | a，c | b，則c |（ka+nb）；若c a，c b，則 c （a+b）。④若ma | mb，則a | b ⑤若a＞0，b＞0，b | a，則b≤a⑥若n∈N*，則（a－b）|（an－bn）。若n為奇數(shù)，則（a＋b

10、）|（an＋bn）。若n為偶數(shù)，則（a＋b）|（an－bn）⑦任意n個(gè)連續(xù)正整數(shù)的乘積必能被n！整除。,分解整數(shù),一個(gè)正整數(shù)有時(shí)可以分解成若干連續(xù)正整數(shù)之和，如15=1+2+3+4+5，有時(shí)這種分解方法不止一種，如15還可以分解成4+5+6和7+8兩種，但有些正整數(shù)就不能分解，如16就不能分解。輸入正整數(shù)N，求出一個(gè)它的所有分解。數(shù)據(jù)規(guī)模：N≤109,,分析：設(shè)可以分解的是a,a+1,…,b，即n=a+(a+1)+…+b則n=

11、(a+b)(b-a+1)/2即(a+b)和(b-a+1)是2*n的一對(duì)因子。窮舉(b-a+1)這個(gè)因子的可能就行了， O(n 1/2)級(jí)的，另外，注意(a+b)和(b-a+1)的奇偶性不同。,立體切割,將一個(gè)長(zhǎng)方體形狀的物體切割成大小相等的n塊，有多種切割方法。我們要求給出這樣一種方法，假設(shè)長(zhǎng)方體的邊長(zhǎng)均為正整數(shù)，要求切割之后，每塊仍然是長(zhǎng)方體，且其邊長(zhǎng)也是正整數(shù)；給出原始長(zhǎng)方體的長(zhǎng)a、寬b、高c和要求分割的塊數(shù)n，求切割之后

12、的長(zhǎng)方體的長(zhǎng)x、寬y、高z，使x+y+z的和最小。數(shù)據(jù)規(guī)模：a,b,c≤1000，n≤1000。,,分析：要使切割之后的長(zhǎng)寬高之和越小，則必須使它們之間的差越小算法：將n分解質(zhì)因數(shù)(多重因子各計(jì)一次)，在將a,b,c從大到小排序后，消去n的最大因子；消去之后的a,b,c再排序消去，直到n的所有因子都被消去，則此時(shí)的分割最優(yōu)。,互質(zhì),當(dāng)（a，b）=1時(shí)，稱a、b互素（互質(zhì)）。,基本性質(zhì),①已知(a，c)=1，若a | bc，則a |

13、 b； 若a | b，c | b，則ac | b②p為素?cái)?shù)，若p | ab，則p | a或p | b ③[a，b]·(a，b)=ab④(a，b)=(a，b－ac)=(a－bc，b)⑤存在整數(shù)x、y，使ax+by=(a，b)⑥m(a，b)=(ma，mb)⑦若(a，b)=d，則=1⑧若a | m，b | m，則[a，b] | m ⑨m[a，b]=

14、[ma，mb],同余,設(shè)m是正整數(shù)，叫做模，若m|(a-b)，稱a，b對(duì)模m同余，記作a≡b（mod m）,基本性質(zhì),①a≡a（mod m） ②若a≡b（mod m），則b≡a（mod m）③若a≡b（mod m），b≡c（mod m），則a≡c（mod m）④若a≡b（mod m），c≡d（mod m），則a±c≡b±d（mod m），ac≡bd（mod m）⑤若n|m，a≡b（mod m），則a≡b（

15、mod n）⑥若（m，n）=1，a≡b（mod m），a≡b（mod n），則a≡b（mod mn）⑦若a≡b（mod m），n∈N*，則an≡bn（mod m）⑧若ac≡bc（mod m），(c，m)=d，則a≡b（mod m/d ）,,⑨ Fermat小定理：p是素?cái)?shù)，則ap≡a（mod p）Euler函數(shù) 我們用 表示小于m的正整數(shù)中與m互質(zhì)的數(shù)的個(gè)數(shù).Fermat小定理的Euler推廣：若a與m互質(zhì)，那么 a

16、^ ≡1 (mod m) 。,,,質(zhì)數(shù)和質(zhì)因子分解,質(zhì)數(shù)（素?cái)?shù)）質(zhì)因子分解算術(shù)基本定理：任何一個(gè)大于1的整數(shù)都可以分解成素?cái)?shù)的乘積。如果不考慮這些素因子的次序，則這種分解法是唯一的。 即對(duì)任一整數(shù)a＞1，有a= p1a1p2a2…pnan ，其中p1<p2<…<pn均為素?cái)?shù)，而a1,a2…,an是正整數(shù)。,,,,幾個(gè)公式,,,,,a的正約數(shù)的個(gè)數(shù)為a的正約數(shù)的和為

17、 * *a的歐拉函數(shù)為,,n的質(zhì)因數(shù)分解,k=2; while (k*k1) …//再對(duì)分解最后的那個(gè)質(zhì)數(shù)進(jìn)行處理,求n的約數(shù)個(gè)數(shù),int nums(int n){ int k, res, p; k=2; res=1; while (k*k1) res*=2; return res;},求n的約數(shù)和

18、,int sum ( int n ){ int k, res, tmp; k=2; res=1; while (k*k1) res*=(1+a); return res;},求歐拉函數(shù),int eular(int n){ int k,res; k=2; res=n; while (k*k1) res=res/n*(n-1); return res;},

19、分?jǐn)?shù)分解,類似于埃及分?jǐn)?shù)，我們對(duì)1/n進(jìn)行分解。不過(guò)在這里，我們只把它分解成兩個(gè)分子為1的分?jǐn)?shù)之和：1/n=1/x+1/y，要求x、y、n均為正整數(shù)，且x<＝y(tǒng)。給定n值，編程統(tǒng)計(jì)有多少對(duì)這樣的x和y。數(shù)據(jù)規(guī)模：2≤n≤109。,,分析：對(duì)這個(gè)分式進(jìn)行變形：1/n=1/x+1/y ? xy=nx+ny ? n2=(x-n)(y-n)于是，問(wèn)題變成了求n2的所有因子個(gè)數(shù)除以2,求n!的質(zhì)因數(shù)分解,分析：N!=1*2*…*

20、n是一個(gè)大整數(shù)。n!分解質(zhì)因數(shù)之后，質(zhì)因子p的重?cái)?shù)公式：[n/p]+[n/p^2]+[n/p^3]+…int fact(int n, int p){ int res=0; while (n>0) res+=n/=p; return res;},n!尾部有多少連續(xù)的0,數(shù)據(jù)規(guī)模：n≤109分析：n!的尾部連續(xù)0與n!中因子5的重?cái)?shù)有關(guān)，直接調(diào)用上述函數(shù)即可。,求組合數(shù)C

21、(n,k)的奇偶性,數(shù)據(jù)規(guī)模：n,k≤109分析： O(logn)的算法C(n,k)的公式為n!/(k!*(n-k)!)直接調(diào)用上述公式即可求出fact(n,2)-fact(k,2)-fact(n-k,2)，如果上式為0,則為奇數(shù)，否則為偶數(shù)。O(1)的算法：若n&k==k，則C(n,k)為奇數(shù)，否則為偶數(shù)。(&:按位與運(yùn)算),楊輝三角,統(tǒng)計(jì)楊輝三角第n行中不能被p整除的數(shù)的個(gè)數(shù)(n≤109)。第n行的每個(gè)數(shù)

22、寫成C(n,i)，可以使用上述辦法，但會(huì)超時(shí)。將n分成兩部分：i和n-i，當(dāng)這三個(gè)數(shù)階乘分解成p的重?cái)?shù)之差相等時(shí)，為奇數(shù)，否則為偶數(shù)。,,,分析：將n轉(zhuǎn)換成p進(jìn)制，再進(jìn)行求解。如求第48行中不能被3整除的數(shù)。將48轉(zhuǎn)換成3進(jìn)制為 (1210)3則48!中3的重?cái)?shù)為 (121)3+(12)3+(1)3將48分成兩部分i和48-i，當(dāng)i的3進(jìn)制中每一位都不超過(guò)48的3進(jìn)制中相應(yīng)的位，n-i的3進(jìn)制也是如此。此時(shí)，i!和(n-i)

23、!中因子3的重?cái)?shù)之和就不超過(guò)(121)3+ (12)3+(1)3,,這樣的i和n-i有多少種呢？i在p進(jìn)制下每一位都不超過(guò)n在p進(jìn)制下的每一位的值，則i的每一位都從0開始，一直取到n在p進(jìn)制下對(duì)應(yīng)位的數(shù)值。將n轉(zhuǎn)換成p進(jìn)制后，所有位加1之后的連乘積就是所求。,密碼,一個(gè)數(shù)列E={E[1],E[2],……,E[n]}，且E[1]=E[2]=p（p為一個(gè)質(zhì)數(shù)），E[i]=E[i-2]*E[i-1] （若2<i<=n）。例如{

24、2,2,4,8, 32,256, 8192,……}就是p=2的數(shù)列。在此基礎(chǔ)上有一種加密算法，該算法通過(guò)一個(gè)密鑰q (q<p)將一個(gè)正整數(shù)n加密成另外一個(gè)正整數(shù)d，計(jì)算公式為：d=E[n] mod q。現(xiàn)在對(duì)于輸入的p,q和m個(gè)正整數(shù)n，求出對(duì)每一個(gè)n加密后的d。數(shù)據(jù)規(guī)模：p,n<231；0<m≤5000,,分析：題目意思很明確，E數(shù)列為p的冪序列，且冪恰好是Fibonacci序列，現(xiàn)在求m個(gè)p^fib(n) %q

25、，從數(shù)據(jù)規(guī)模上來(lái)看，較難實(shí)現(xiàn)。1、fib(n)，當(dāng)n為109時(shí)，利用矩陣算法2、歐拉函數(shù)，當(dāng)p與q互質(zhì)時(shí)，p^ψ(q) ≡1 (mod q)，即p^ψ(q) %q=13、1)2)結(jié)合，利用矩陣算法求t=fib(n)% ψ(q)的值，所求結(jié)果為p^t ≡ p^fib(n) (mod q)4、t可能也很大，利用快速冪的算法（實(shí)際上矩陣算法已經(jīng)用到了）,細(xì)胞分裂,NOIP2009PJ第三題N個(gè)細(xì)胞，每種細(xì)胞的分裂速度為一秒鐘分裂Si

26、個(gè)，問(wèn)能否均分m1^m2，如果能的話，求最短的用時(shí)。數(shù)據(jù)規(guī)模：N≤10000,m1 ≤30000,m2 ≤10000,Si ≤2000000000,,分析：分裂速度為每一秒Si，表示第k秒后，它會(huì)分裂成Si^k個(gè)細(xì)胞，即問(wèn)它是否能整除m1 ^m2先將m1^m2分解質(zhì)因數(shù)，對(duì)于它的某個(gè)質(zhì)因子pi的因子重?cái)?shù)為ti，用pi除Si的重?cái)?shù)ui應(yīng)滿足k*ui>=ti，找出所有的k的最大值，就是Si的時(shí)間。而所有Si的時(shí)間中，最小值就是本

27、題的答案。,Hankson 的趣味題,NOIP2009TG第二題已知(x,a0)=a1,[x,b0]=b1，求x的所有可能方案數(shù)。共n組測(cè)試數(shù)據(jù)數(shù)據(jù)規(guī)模：n≤2000, a0,a1,b0,b1 ≤2000000000,,分析：分解質(zhì)因數(shù)將b1分解因數(shù)，它的某個(gè)質(zhì)因子pi，重?cái)?shù)為t1,對(duì)b0,a0,a1同樣也對(duì)pi進(jìn)行分解，重?cái)?shù)分別為t2,t3,t4，則x對(duì)pi的重?cái)?shù)u應(yīng)該滿足：u 與t2的較大值為t1，u與t3的較小值應(yīng)為t