OI中的数论 芜湖 汪从文.pptVIP

OI中的初等数论入门 芜湖 汪从文 进位计数制 进制表示 表示b进制下的n位数。 b进制向十进制转换： 乘以基数并展开： 天平I 一个天平，砝码分别为1g、3g、9g、27g、…6561g…，每个砝码只有一个，要称重的物品放在天平的左侧，而砝码允许放在天平的左右两侧。已知一个物品的质量N，问如何称重？ 数据规模：N≤108 分析： 就是将N转换成三进制后，将三进制中的0、1、2三个状态转换成 0、1 、-1 ，具体的说，就是0和1不变，2变成-1后，其高一位加1。 天平II 一个天平，砝码分别为1g、3g、9g、27g、… 6561g…，每个砝码只有一个，要称重的物品放在天平的左侧，而砝码只允许放在天平的右侧。将由这个系统可以称出来的重量按从小到大的顺序进行排列，得到下列序列：1,3,4,9,10,...。问其中的第K个重量是多少？ 数据规模：K≤105 分析： 这就是NOIP2006PJ《序列》中p=3时的简化版 将K转换成二进制并按三(p=3)进制展开。 倒水 一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着CC他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，合并并丢弃一个空瓶（不能丢弃有水的瓶子）。显然在某些情况下CC无法达到目标。此时CC会重新买一些新的瓶子（新瓶子容量无限，开始时有1升水），以达到目标。问最少需要买多少新瓶子才能达到目标呢？ 数据规模：N≤109,K≤1000 分析： 根据题意，保留的瓶子的水容量一定为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; 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加，表示将n按b进制下的逆序展开。 进制回文数 输入一个正整数N，求从1到N中十进制、二进制和八进制均为回文数的数字个数。注意：一位数也是回文数。 数据规模：N≤1000000。 回文平方数 给定一个进制B(2≤B≤20,由十进制表示)和N，输出所有的大于等于1小于等于N（十进制下）且它的平方用B进制表示时是回文数的数。用’A’,’B’……表示10，11等等。 数据规模：N≤100000 第i个回文数 求第i个回文数 数据规模：i≤109 分析： 注意回文数的特点：1~9为最初的9个回文数，11~99为其次的9个回文数，为1~9进行翻转而得到；依此类推，可以得到所有的回文数。 整除 设 a,b为整数，a≠0. 若有一整数q, 使得 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 ⑤若a＞0，b＞0，b | a，则b≤a ⑥若n∈N*，则（a－b）|（an－bn）。 若n为奇数，则（a＋b）|（an＋bn）。 若n为偶数，则（a＋b）|（an－bn） ⑦任意n个连续正整数的乘积必能被n！整除。 分解整数 一个正整数有时可以分解成若干连续