oi中的數(shù)論 (1)

1、OI中的初等數(shù)論入門,蕪湖 汪從文,進(jìn)位計數(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ù)部分。,一個天平，砝碼分別為1g、3g、9g、27g、…6561g…，每個砝碼只有一個，要稱重的物品放在天平的左側(cè)，而砝碼允許放在天平的左右兩側(cè)。已知一個物品的質(zhì)量N，問如何稱重？數(shù)據(jù)規(guī)模：N≤108,天平I,分

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

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

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

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

6、 while (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){ //判斷

7、n在b進(jìn)制下是否為回文數(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)制下的逆序展開。,輸入一個正整數(shù)N，求從1到N中十進(jìn)制、二進(jìn)制和八進(jìn)制均為回文數(shù)的數(shù)字個數(shù)。注意：一位數(shù)也是回文數(shù)。數(shù)據(jù)規(guī)模：N≤1000000。,進(jìn)制回文數(shù),給定一個進(jìn)制B(2≤B≤20,由

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

9、q, 則稱 a是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為

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

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

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

13、 bc，則a | b； 若a | b，c | b，則ac | b②p為素數(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

14、⑨m[a，b]=[ma，mb],同余,設(shè)m是正整數(shù)，叫做模，若m|(a-b)，稱a，b對模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

15、m），則a≡b（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是素數(shù)，則ap≡a（mod p）Euler函數(shù) 我們用 表示小于m的正整數(shù)中與m互質(zhì)的數(shù)的個數(shù).Fermat小定理的Euler推廣：若a與

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

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

18、},求n的約數(shù)和,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/a*(a-1); return

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

20、!=1*2*…*n是一個大整數(shù)。n!分解質(zhì)因數(shù)之后，質(zhì)因子p的重數(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的重數(shù)有關(guān)，直接調(diào)用上述函數(shù)即

21、可。,求組合數(shù)C(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ù)。(&:按位與運算),楊輝三角,統(tǒng)計楊輝三角第n行中不能被p整除的數(shù)的個數(shù)(n≤109)。

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

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

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

25、ib(n) %q，從數(shù)據(jù)規(guī)模上來看，較難實現(xiàn)。1、fib(n)，當(dāng)n為109時，利用矩陣算法2、歐拉函數(shù)，當(dāng)p與q互質(zhì)時，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可能也很大，利用快速冪的算法（實際上矩陣算法已經(jīng)用到了）,細(xì)胞分裂,NOIP2009PJ第三題N個細(xì)胞，每種細(xì)胞的分裂速度

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

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