oi中的初等数论(一)

《oi中的初等数论(一)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、OI中的初等数论一、进位计数制进制表示表示b进制下的n位数。b进制向十进制转换：乘以基数并展开：inthex10(charnum[],intlen,intb){//n位长度的b进制数以字符形式存入num数组，转换成十进制inti,res=0;for(i=0;i10，则需要写成：//res=res*b+num[i]-'a'+10;returnres;}十进制向b进制转换：除以基数并倒取余数。inthexb(charnum[],intdec,intb){//将十进制数dec转换成b进制，并以字符存入num数组，返回其长度

2、//存入num数组时，低位存入下标0中intlen=0;while(dec>0){num[len++]='0'+dec%b;num/=b;}//如果b>10，则需要处理余数>10的情况，略returnlen;}例题1、天平I问题描述：一个天平，砝码分别为1g、3g、9g、27g、…6561g，每个砝码只有一个，要称重的物品放在天平的左侧，而砝码允许放在天平的左右两侧。已知一个物品的重量，问如何称重？试编程解决。输入格式：一个重量N（1≤N≤10000）输出格式：将所使用的砝码重量，按从大到小的顺序输出。其中与物品异侧的砝码用正号表示，与物品同侧的砝码用负号表示。（第一个砝码前的正号要省略

3、）样例输入：15样例输出：27-9-3分析：就是将N转换成三进制后，将三进制中的0、1、2三个状态转换成-1、0、1，具体的说，就是0和1不变，2变成-1后，向高位倒借1。intwork(inta[],intn){//将n转换成特殊的三进制intlen=0;memset(a,0,sizeof(a));while(n>0){a[len++]=n%3;n/=3;}for(i=0;i1){a[i]-=3;a[i+1]++;}if(a[len]!=0)len++;returnlen;}2、天平II：问题描述：一个天平，砝码分别为1g、3g、9g、27g、…656

4、1g，每个砝码只有一个，要称重的物品放在天平的左侧，而砝码只允许放在天平的右侧。这样，肯定有一些物品是无法称重的，例如重量为5g的物品就是无法称出来的。现在将由这个系统可以称出来的重量按从小到大的顺序进行排列，得到下列序列：1,3,4,9,10,12,13,27,28,30,31,36,37,39,40,...。问其中的第K个重量是多少？输入格式：仅一个整数K（1≤K≤105）输出格式：仅一个整数，表示对应的第K个重量。样例输入：15样例输出：40分析：这就是NOIP2006PJ的最后一题《序列》中p=3时的简化版。就是将K转换成二进制并按三进制展开。intwork(intn,intp)

5、{//将n转换成二进制，并按p进制展开成十进制intt,res;t=1;res=0;while(n>0){if(n%2==1)res+=t;n/=2;t*=p;}returnres;}3、倒水问题描述：一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着CC他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，把一个瓶子的水全部倒进另一个里，然后把空瓶丢弃。（不能丢弃有水的瓶子）显然在某些情况下CC无法达到目标，比如N=3,K=1。此时CC会重新买一些新的瓶子（新瓶子容量无限，开始时有1升水），以达到目标。现在CC想知道，最少需要买多少新瓶子才能达到目标呢

6、？输入格式：一行两个正整数N,K（1≤N≤10^9,K≤1000）。输出格式：仅一个非负整数，表示最少需要买多少新瓶子。样例输入：10000005样例输出：15808分析：根据题意，保留的瓶子的水容量一定为2的方幂，就是求N的二进制形式中，从高位到低位保留K位1，所需要补充的最小差值。intwork(intn,intk){inti,a[32],res;for(i=0;i<31;i++)a[i]=1<0&&k>1){if(n>a[i]){n-=a[i];k--;}i--;}if(n==0)return0;i=0;while(n>a[i])i++;return

7、a[i]-n;}