资源描述：
《OI中的数论.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、OI中的初等数论入门进位计数制进制表示表示b进制下的n位数。b进制向十进制转换：乘以基数并展开：十进制向b进制转换：整数部分除以基数并倒取余数。小数部分乘以基数，并顺取整数部分。一个天平，砝码分别为1g、3g、9g、27g、…6561g…，每个砝码只有一个，要称重的物品放在天平的左侧，而砝码允许放在天平的左右两侧。已知一个物品的质量N，问如何称重？数据规模：N≤108天平I分析：就是将N转换成三进制后，将三进制中的0、1、2三个状态转换成0、1、-1，具体的说，就是0和1不变，2变成-1后，其高一位加1。一个天平，砝码分别为1g、3g、9
2、g、27g、…6561g…，每个砝码只有一个，要称重的物品放在天平的左侧，而砝码只允许放在天平的右侧。将由这个系统可以称出来的重量按从小到大的顺序进行排列，得到下列序列：1,3,4,9,10,...。问其中的第K个重量是多少？数据规模：K≤105天平II分析：这就是NOIP2006PJ《序列》中p=3时的简化版将K转换成二进制并按三(p=3)进制展开。一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着CC他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，合并并丢弃一个空瓶（不能丢弃有水的瓶子）。显然在
3、某些情况下CC无法达到目标。此时CC会重新买一些新的瓶子（新瓶子容量无限，开始时有1升水），以达到目标。问最少需要买多少新瓶子才能达到目标呢？数据规模：N≤109,K≤1000倒水分析：根据题意，保留的瓶子的水容量一定为2的方幂，就是求N的二进制形式中，从高位到低位保留K位1，所需要补充的最小差值。例如N=27=(11011)2,k=3时数字分离及回文数数字分离用于统计整数数码、位数、逆序等while(n>0){//n%10就是n的每一位数字n/=10;}intcont(intn){//统计n的位数ints=0;while(n>0){s+
4、+;n/=10;}returns;}intsum(intn){//统计n的数字和ints=0;while(n>0){s+=n%10;n/=10;}returns;}intrev(intn){//计算n的逆序数ints=0;while(n>0){s=s*10+n%10;n/=10;}returns;}boolpal(intn){//判断n是否为回文数ints=0,m=n;while(n>0){s=s*10+n%10;n/=10;}returns==m;}boolpalb(intn,intb){//判断n在b进制下是否为回文数ints=0,m
5、=n;while(n>0){s=s*b+n%b;n/=b;}returns==m;}注意：循环内的乘b加，表示将n按b进制下的逆序展开。输入一个正整数N，求从1到N中十进制、二进制和八进制均为回文数的数字个数。注意：一位数也是回文数。数据规模：N≤1000000。进制回文数给定一个进制B(2≤B≤20,由十进制表示)和N，输出所有的大于等于1小于等于N（十进制下）且它的平方用B进制表示时是回文数的数。用’A’,’B’……表示10，11等等。数据规模：N≤100000回文平方数求第i个回文数数据规模：i≤109分析：注意回文数的特点：1~9
6、为最初的9个回文数，11~99为其次的9个回文数，为1~9进行翻转而得到；依此类推，可以得到所有的回文数。第i个回文数整除设a,b为整数，a≠0.若有一整数q,使得b=aq,则称a是b的因数，b为是a的倍数；并称a整除b,记为a
7、b；若a不能整除b，则记为ab。基本性质①若c
8、b，b
9、a，则c
10、a②若c
11、a，d
12、b，则cd
13、ab③若c
14、a，c
15、b，则c
16、（ka+nb）；若ca，cb，则c（a+b）。④若ma
17、mb，则a
18、b⑤若a＞0，b＞0，b
19、a，则b≤a⑥若n∈N*，则（a－b）
20、（an－bn）。若n为奇数，则（a＋b）
21、（an＋bn
22、）。若n为偶数，则（a＋b）
23、（an－bn）⑦任意n个连续正整数的乘积必能被n！整除。分解整数一个正整数有时可以分解成若干连续正整数之和，如15=1+2+3+4+5，有时这种分解方法不止一种，如15还可以分解成4+5+6和7+8两种，但有些正整数就不能分解，如16就不能分解。输入正整数N，求出一个它的所有分解。数据规模：N≤109分析：设可以分解的是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(n1/2)级的，另
24、外，注意(a+b)和(b-a+1)的奇偶性不同。立体切割将一个长方体形状的物体切割成大小相等的n块，有多种切割方法。我们要求给出这样一种方法，假设长方体的边长均为正整数，要求切割之后，每块仍然
