OI中的数论 (1)

1、OI中的初等数论入门,芜湖 汪从文,进位计数制,进制表示 表示b进制下的n位数。,b进制向十进制转换： 乘以基数并展开：,十进制向b进制转换： 整数部分除以基数并倒取余数。 小数部分乘以基数，并顺取整数部分。,一个天平，砝码分别为1g、3g、9g、27g、6561g，每个砝码只有一个，要称重的物品放在天平的左侧，而砝码允许放在天平的左右两侧。已知一个物品的质量N，问如何称重？ 数据规模：N108,天平I,分析： 就是将N转换成三进制后，将三进制中的0、1、2三个状态转换成 0、1 、-1 ，具体的说，就是0和1不变，2变成-1后，其高一位加1。,一个天平，砝码分别为1g、3g、9g、27g、

2、6561g，每个砝码只有一个，要称重的物品放在天平的左侧，而砝码只允许放在天平的右侧。将由这个系统可以称出来的重量按从小到大的顺序进行排列，得到下列序列：1,3,4,9,10,.。问其中的第K个重量是多少？ 数据规模：K105,天平II,分析： 这就是NOIP2006PJ序列中p=3时的简化版 将K转换成二进制并按三(p=3)进制展开。,一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着CC他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，合并并丢弃一个空瓶（不能丢弃有水的瓶子）。显然在某些情况下CC无法达到目标。此时CC会重新买一些新的瓶子（新瓶子容量无

3、限，开始时有1升水），以达到目标。问最少需要买多少新瓶子才能达到目标呢？ 数据规模：N109,K1000,倒水,分析： 根据题意，保留的瓶子的水容量一定为2的方幂，就是求N的二进制形式中，从高位到低位保留K位1，所需要补充的最小差值。 例如N=27=(11011)2,k=3时,数字分离及回文数,数字分离 用于统计整数数码、位数、逆序等 while (n0) / n%10 就是n的每一位数字 n/=10; ,int cont(int n)/统计n的位数 int s=0; while (n0) s+; n/=10; return s; int sum(int n)/统计n的数字和 int s=0;

4、 while (n0) s+=n%10; n/=10; return s; ,int rev(int n)/计算n的逆序数 int s=0; while (n0) s=s*10+n%10; n/=10; return s; bool pal(int n)/判断n是否为回文数 int s=0,m=n; while (n0) s=s*10+n%10; n/=10; return s=m; ,bool palb(int n,int b) /判断n在b进制下是否为回文数 int s=0,m=n; while (n0) s=s*b + n%b; n/=b; return s=m; 注意：循环内的乘b加，

5、表示将n按b进制下的逆序展开。,输入一个正整数N，求从1到N中十进制、二进制和八进制均为回文数的数字个数。注意：一位数也是回文数。 数据规模：N1000000。,进制回文数,给定一个进制B(2B20,由十进制表示)和N，输出所有的大于等于1小于等于N（十进制下）且它的平方用B进制表示时是回文数的数。用A,B表示10，11等等。 数据规模：N100000,回文平方数,求第i个回文数 数据规模：i109 分析： 注意回文数的特点：19为最初的9个回文数，1199为其次的9个回文数，为19进行翻转而得到；依此类推，可以得到所有的回文数。,第i个回文数,整除,设 a,b为整数，a0. 若有一整数q,

6、使得 b = aq, 则称 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 若a0，b0，b | a，则ba 若nN*，则（ab）|（anbn）。 若n为奇数，则（ab）|（anbn）。 若n为偶数，则（ab）|（anbn） 任意n个连续正整数的乘积必能被n！整除。,分解整数,一个正整数有时可以分解成若干连续正整数之和，如15=1+2+3

7、+4+5，有时这种分解方法不止一种，如15还可以分解成4+5+6和7+8两种，但有些正整数就不能分解，如16就不能分解。输入正整数N，求出一个它的所有分解。 数据规模：N109,分析： 设可以分解的是a,a+1,b，即n=a+(a+1)+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块，有多种切割方法。我们要求给出这样一种方法，假设长方体的边长均为正整数，要求切割之后，每块仍然是长方体，

8、且其边长也是正整数；给出原始长方体的长a、宽b、高c和要求分割的块数n，求切割之后的长方体的长x、宽y、高z，使x+y+z的和最小。 数据规模：a,b,c1000，n1000。,分析： 要使切割之后的长宽高之和越小，则必须使它们之间的差越小 算法：将n分解质因数(多重因子各计一次)，在将a,b,c从大到小排序后，消去n的最大因子；消去之后的a,b,c再排序消去，直到n的所有因子都被消去，则此时的分割最优。,互质,当（a，b）=1时，称a、b互素（互质）。,基本性质,已知(a，c)=1，若a | bc，则a | b； 若a | b，c | b，则ac | b p为素数，若p | ab，则p |

9、a或p | b a，b(a，b)=ab (a，b)=(a，bac)=(abc，b) 存在整数x、y，使ax+by=(a，b) m(a，b)=(ma，mb) 若(a，b)=d，则=1 若a | m，b | m，则a，b | m ma，b=ma，mb,同余,设m是正整数，叫做模，若m|(a-b)，称a，b对模m同余，记作ab（mod m）,基本性质,aa（mod m） 若ab（mod m），则ba（mod m） 若ab（mod m），bc（mod m），则ac（mod m） 若ab（mod m），cd（mod m），则acbd（mod m），acbd（mod m） 若n|m，ab（mod m），则

10、ab（mod n） 若（m，n）=1，ab（mod m），ab（mod n），则ab（mod mn） 若ab（mod m），nN*，则anbn（mod m） 若acbc（mod m），(c，m)=d，则ab（mod m/d ）, Fermat小定理：p是素数，则apa（mod p） Euler函数 我们用 表示小于m的正整数中与m互质的数的个数. Fermat小定理的Euler推广：若a与m互质，那么 a 1 (mod m) 。,质数和质因子分解,质数（素数） 质因子分解 算术基本定理：任何一个大于1的整数都可以分解成素数的乘积。如果不考虑这些素因子的次序，则这种分解法是唯一的。 即对任一整数

11、a1，有a= p1a1p2a2pnan ，其中p1p2pn均为素数，而a1,a2,an是正整数。,几个公式,a的正约数的个数为 a的正约数的和为 * * 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; ,求n的约数和,int sum ( int n ) int k, res, tmp; k=2; res=1; while (k*k1) res*=(1+a); return r

12、es; ,求欧拉函数,int eular(int n) int k,res; k=2; res=n; while (k*k1) res=res/a*(a-1); return res; ,分数分解,类似于埃及分数，我们对1/n进行分解。不过在这里，我们只把它分解成两个分子为1的分数之和：1/n=1/x+1/y，要求x、y、n均为正整数，且x0) res+=n/=p; return res; ,n!尾部有多少连续的0,数据规模：n109 分析： n!的尾部连续0与n!中因子5的重数有关，直接调用上述函数即可。,求组合数C(n,k)的奇偶性,数据规模：n,k109 分析： O(logn)的算法 C

13、(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)为奇数，否则为偶数。(&:按位与运算),杨辉三角,统计杨辉三角第n行中不能被p整除的数的个数(n109)。 第n行的每个数写成C(n,i)，可以使用上述办法，但会超时。 将n分成两部分：i和n-i，当这三个数阶乘分解成p的重数之差相等时，为奇数，否则为偶数。,分析：将n转换成p进制，再进行求解。 如求第48行中不能被3整除的数。 将48转换成3进制为 (1210)3 则48!中

14、3的重数为 (121)3+(12)3+(1)3 将48分成两部分i和48-i，当i的3进制中每一位都不超过48的3进制中相应的位，n-i的3进制也是如此。 此时，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=E1,E2,En，且E1=E2=p（p为一个质数），Ei=Ei-2*Ei-1 （若2i=n）。例如2,2,4,8, 32,256, 8192,就是p=2的数列。在此基础上有一种加密算法，该算法通过一个密钥q (qp)将一个正整数n加密成另外一个正整数d，计算公式为：d=En mod q。现在对于输入的p,q和m个正整数n，求出对每一个n加密后的d。 数据规模：p,n231；0=ti，找出所有的k的最大值，就是Si的时间。而所有Si的时间中，最小值就是本题的答案。