OI中的初等数论(一).doc

OI中的初等数论一、进位计数制进制表示表示b进制下的n位数。b进制向十进制转换：乘以基数并展开：int hex10(char num, int len, int b) /n位长度的b进制数以字符形式存入num数组，转换成十进制 int i, res=0; for (i=0; i10，则需要写成： /res = res*b + numi- a+10; return res; 十进制向b进制转换：除以基数并倒取余数。int hexb(char num, int dec, int b) /将十进制数dec转换成b进制，并以字符存入num数组，返回其长度 /存入num数组时，低位存入下标0中 int len=0; while (dec0) numlen+=0+dec%b; num /= b; /如果b10，则需要处理余数10的情况，略 return len;例题1、天平I问题描述：一个天平，砝码分别为1g、3g、9g、27g、6561g，每个砝码只有一个，要称重的物品放在天平的左侧，而砝码允许放在天平的左右两侧。已知一个物品的重量，问如何称重？试编程解决。输入格式：一个重量N（1N10000）输出格式：将所使用的砝码重量，按从大到小的顺序输出。其中与物品异侧的砝码用正号表示，与物品同侧的砝码用负号表示。（第一个砝码前的正号要省略）样例输入：15样例输出：27-9-3分析：就是将N转换成三进制后，将三进制中的0、1、2三个状态转换成-1、0、1，具体的说，就是0和1不变，2变成-1后，向高位倒借1。int work(int a,int n)/将n转换成特殊的三进制 int len=0; memset(a,0,sizeof(a); while (n0) alen+=n%3; n/=3; for (i=0;i1) ai-=3; ai+1+; if (alen!=0) len+; return len;2、天平II：问题描述：一个天平，砝码分别为1g、3g、9g、27g、6561g，每个砝码只有一个，要称重的物品放在天平的左侧，而砝码只允许放在天平的右侧。这样，肯定有一些物品是无法称重的，例如重量为5g的物品就是无法称出来的。现在将由这个系统可以称出来的重量按从小到大的顺序进行排列，得到下列序列：1,3,4,9,10,12,13,27,28, 30,31,36,37,39,40,.。问其中的第K个重量是多少？输入格式：仅一个整数K（1K105）输出格式：仅一个整数，表示对应的第K个重量。样例输入：15样例输出：40分析：这就是NOIP2006PJ的最后一题序列中p=3时的简化版。就是将K转换成二进制并按三进制展开。int work(int n, int p)/将n转换成二进制，并按p进制展开成十进制 int t,res; t=1; res=0; while (n0) if (n%2=1) res+=t; n/=2; t*=p; return res;3、倒水问题描述：一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着CC他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，把一个瓶子的水全部倒进另一个里，然后把空瓶丢弃。（不能丢弃有水的瓶子）显然在某些情况下CC无法达到目标，比如N=3,K=1。此时CC会重新买一些新的瓶子（新瓶子容量无限，开始时有1升水），以达到目标。现在CC想知道，最少需要买多少新瓶子才能达到目标呢？输入格式：一行两个正整数N,K（1N109,K1000）。输出格式：仅一个非负整数，表示最少需要买多少新瓶子。样例输入：1000000 5样例输出：15808分析：根据题意，保留的瓶子的水容量一定为2的方幂，就是求N的二进制形式中，从高位到低位保留K位1，所需要补充的最小差值。int work(int n, int k) int i, a32, res; for ( i=0; i31; i+ ) ai=10 &