oi中的數論 (1)

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

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

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

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

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

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

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

9、q, 則稱 a是b的因數，b為是a的倍數；并稱a整除b, 記為a|b；若a不能整除b，則記為a b。,基本性質,①若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、奇數，則（a＋b）|（an＋bn）。若n為偶數，則（a＋b）|（an－bn）⑦任意n個連續(xù)正整數的乘積必能被n！整除。,分解整數,一個正整數有時可以分解成若干連續(xù)正整數之和，如15=1+2+3+4+5，有時這種分解方法不止一種，如15還可以分解成4+5+6和7+8兩種，但有些正整數就不能分解，如16就不能分解。輸入正整數N，求出一個它的所有分解。數據規(guī)模：N≤109,,分析：設可以分解的是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塊，有多種切割方法。我們要求給出這樣一種方法，假設長方體的邊長均為正整數，要求切割之后，每塊仍然是長方體，且其邊長也是正整數；給出原始長方體的長a、寬b、高c和要求分割的塊

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

13、 bc，則a | b； 若a | b，c | b，則ac | b②p為素數，若p | ab，則p | a或p | b ③[a，b]·(a，b)=ab④(a，b)=(a，b－ac)=(a－bc，b)⑤存在整數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],同余,設m是正整數，叫做模，若m|(a-b)，稱a，b對模m同余，記作a≡b（mod m）,基本性質,①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是素數，則ap≡a（mod p）Euler函數 我們用 表示小于m的正整數中與m互質的數的個數.Fermat小定理的Euler推廣：若a與

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

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

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

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

20、!=1*2*…*n是一個大整數。n!分解質因數之后，質因子p的重數公式：[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,數據規(guī)模：n≤109分析：n!的尾部連續(xù)0與n!中因子5的重數有關，直接調用上述函數即

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

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

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

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

25、ib(n) %q，從數據規(guī)模上來看，較難實現。1、fib(n)，當n為109時，利用矩陣算法2、歐拉函數，當p與q互質時，p^ψ(q) ≡1 (mod q)，即p^ψ(q) %q=13、1)2)結合，利用矩陣算法求t=fib(n)% ψ(q)的值，所求結果為p^t ≡ p^fib(n) (mod q)4、t可能也很大，利用快速冪的算法（實際上矩陣算法已經用到了）,細胞分裂,NOIP2009PJ第三題N個細胞，每種細胞的分裂速度

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

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