无双题解

# NENUOJ 之 算法1第5章

# 5001 特殊的四位数 (opens new window)

# 题目描述

找出并输出所有小于等于n的4位数（十进制数）中具有如下属性的数：四位数字之和等于其十六进制形式各位数字之和，也等于其十二进制形式各位数字之和。 例如：十进制数2991，其四位数字之和2+9+9+1 = 21。由于2991 = 1 * 1728 + 8 * 144 + 9 * 12 + 3，其十二进制形式为1893(12), 其各位数字之和也为21。但是它的十六进制形式为BAF(16)，其各位数字之和等于11+10+15 = 36。因此你的程序要舍去2991这个数据。 下一个数2992，其十进制、十二进制、十六进制形式各位数字之和均为22，因此2992符合要求，应该输出来。（只考虑4位数，2992是第一个符合要求的数）

# 输入

输入有多行，每行一个正整数n（四位整数）。

# 输出

你的程序要求输出满足要求的四位数（要求严格按升序输出），每个数占一行（前后都没有空行），整个输出以换行符结尾。输出中没有空行。输出中的前几行如输出样例所示。如果没有则输出0。

# 样例输入 复制

2000
3000

# 样例输出 复制

0
2992
2993
2994
2995
2996
2997
2998
2999

# 思路：

写习惯进制转换的函数就好~算是一道比较基础的进制转换题目。

# 代码C语言：

#include<stdio.h>
int find(int n,int base){
    int sum = 0;
    while(n > 0){
        sum += n % base;
        n /= base;
    }
    return sum;
}
int main(){
    int n;
    while(~scanf("%d",&n)){
        int flag = 0;
        for(int i = 1000;i <= n;i++){
            int sum = find(i,10);
            int sum12 = find(i,12);
            int sum16 = find(i,16);
            if(sum == sum12 && sum == sum16){
                printf("%d\n", i);
                flag = 1;
            }
        }
        if(!flag){
            flag = 0;
            printf("0\n");
        }
    }
    return 0;
}

# 5002 进制转换 (opens new window)

# 题目描述

输入一个十进制数N，将它转换成R进制数输出。

# 输入

输入数据包含多个测试实例，每个测试实例包含两个整数N（32位整数）和R（2<=R<=16，R != 10）。

# 输出

为每个测试实例输出转换后的数，每个输出占一行。如果R大于10，则对应的数字规则参考16进制（比如，10用A表示，等等）。

# 样例输入 复制

7 2
23 12
-4 3

# 样例输出 复制

111
1B
-11

# 思路：

十进制转R进制，首先需要有个数组存储进制值，如下方代码的temp数组一样。

然后用个while循环不断除以进制数R，就能得到序列了，最后输出即可。详情看代码~

# 代码C语言：

#include<stdio.h>
#include<string.h>
char temp[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
void jinzhi(char str[],int n,int r){
    int flag = 0;
    if(n < 0){
        n = -n;
        flag = 1;
    }
    int i = 0;
    while(n){
        str[i++] = temp[n % r];
        n /= r;
    }
    if(flag == 1) printf("-");
    for(int j = i - 1;j >= 0;j--){
        printf("%c",str[j]);
    }
}
int main(){
    
    int n,r;
    char str[10000];
    while(~scanf("%d %d",&n,&r)){
        jinzhi(str,n,r);
        printf("\n");
    }
    

    return 0;
}

# 5003 skew数 (opens new window)

# 题目描述

在skew 二进制数表示中，第k位的值xk 表示xk * (2k+1-1) 。每个位上的可能数字是0或1，最后面一个非零位可以是2，例如, 10120(skew) = 1 * (25-1) + 0 * (24-1) + 1 * (23-1) + 2 * (22-1) +0 * (21-1) = 31 + 0 + 7 + 6 + 0 = 44. 前十个skew 数是 0、1、2、10、11、12、20、100、101以及102。

# 输入

输入包含一行或多行，每行包含一个整数n。如果n = 0 表示输入结束，否则n 是一个skew 数。

# 输出

对于每一个输入，输出它的十进制表示。转换成十进制后， n 不超过 231-1 = 2 147 483 647。

# 样例输入 复制

10120
200000000000000000000000000000
10
1000000000000000000000000000000
11
100
11111000001110000101101102000
0

# 样例输出 复制

44
2147483646
3
2147483647
4
7
1041110737

# 思路：

按题目意思模拟即可，一位一位处理。

# 代码C语言：

#include<stdio.h>
#include<string.h>
#include<math.h>
int main(){
     
    char str[10000];
    while(~scanf("%s",str)){
        if(str[0] == '0') break;
        int sum = 0;
        int len = strlen(str);
        for(int i = 0;i <= len - 1;i++){
            sum += (str[i]-'0') * (pow(2,len - i) - 1);
        }
        printf("%d\n",sum);
        sum = 0;
    }
 
    return 0;
}

# 5004 周易 (opens new window)

# 题目描述

有人说，中国古代的“周易”是二进制系统的起源，在该系统中，他们用“- -”表示1，“---”表示0。因此，二进制数字“011010”可以表述为“---\n- -\n- -\n---\n- -\n---\n”（符号“\n”表示换行）。现在的问题是如何把一个十进制数转换为“周易”中的二进制？

# 输入

文件中包含多组测试数据。每个测试数据占一行，包括一十进制整数n（0 <= n <= 1000000）和表示二进制位数的k（0 < k <= 20 且 n < 2k）。 n=0，k=0表示输入结束。

# 输出

对于每组测试数据，输出“周易”中对应的k行二进制数。每组测试数据之间输出一个空行。

# 样例输入 复制

7 3
0 3
26 6
0 0

# 样例输出 复制

- -
- -
- -

---
---
---

---
- -
- -
---
- -
---

# 思路：

自行模拟，转换成二进制，遇到1和0输出不一样的。注意，如果k很大，2的k次方超过n，就会有一些0的出现。

# 代码C语言：

#include<stdio.h>
#include<string.h>
#include<math.h>
char str[10000];
char temp[] = {'0','1'};
int main(){
    
    int n,k;
    while(~scanf("%d %d",&n,&k)){
        if(!n && !k) break;
        int i = 0,j = 0;
        //转二进制
        while(n){
            str[i++] = temp[n % 2];
            n /= 2;
        }
        //把超过范围的那部分二进制的0输出了
        if(i < k){
            int len = k - i;
            while(len--){
                printf("---\n");
            }
        }
        
        for(j = i - 1;j >= 0;j--){
            if(str[j]=='1'){
                printf("- -");
            }
            else{
                printf("---");
            }
            printf("\n");
        }
        
        printf("\n");
    }
    return 0;
}

# 5005 奶牛计算器 (opens new window)

# 题目描述

由于缺乏数学经验，奶牛想建立一个计算机器（它被称为Cowmpouter），使用二进制数字（基数为2），但它是建立在-2的基础上。他们非常高兴，因为在-2进制表示的数字中不需要符号位。 你知道基数的权值都是从1开始的（0位），然后从右到左依次为基数1次方，基数2次方等等。在-2进制中，其权值从右到左，依次为1，-2，4，-8，16，-32，…。因此，从1计数依次是：1，110，111，100，101，11010，11011，11000，11001等等。 很怪异的是，负数也那个用1和0表示，但没有符号位。从-1向下计数依次为：11，10，1101，1100，1111等等。 请帮助奶牛把普通的十进制整数（范围为：-2,000,000,000到2,000,000,000）转换为-2进制对应的数。

# 输入

输入只有一行，一个需要转换为-2进制的十进制整数。

# 输出

对应的-2进制的数，没有前导0，0就表示0本身，只用1个0。

# 样例输入 复制

-13

# 样例输出 复制

110111

# 思路：

这道题的思路就是，不断除以-2，然后输出0或者1。然后简单把玩一下数据，大概就能发现奇数偶数处理上的不同，正奇数和负奇数页有所不同，所以就会得到下方代码。

# 代码C语言：

#include<stdio.h>
//转换函数
void convert(int n) {
    if(n == 0) return;
    //如果是偶数，尾数是0
    if(n % 2 == 0) {
        //除以-2，之后补0【因为从右往左】
        convert(-(n / 2));
        printf("0");
    } else {
        //如果是奇数，尾数是1
        //除以-2，之后补1【因为从右往左】
        if(n > 0) convert(-(n / 2));
        else convert(-(n - 1) / 2);
        printf("1");
    }
}

int main() {
    int n;
    scanf("%d", &n);
    if(n == 0) printf("0");
    else convert(n);
    printf("\n");
    return 0;
}

# 5006 计算器设计 (opens new window)

# 题目描述

Really Neato计算器公司最近邀请你的团队为他们设计一款超级Neato一代计算器。作为计算机科学家，你建议该计算器能够在各种进制之间进行转换。他们认为这是一个很好的想法，并要求你的团队先给出实现进制转换的算法原型。公司经理告诉你，该计算器应该具有以下一些特征： （1）可以显示7位； （2）按键除了数字0到9外，还包括大写字母A到F； （3）支持2~16进制。

# 输入

输入文件中的每行为一个进制转换，包括3个数，第1个数是原进制下的一个整数，第2个数就是原进制，第3个数是转换后的进制。这3个数的两边可能有一个或多个空格。输入数据一直到文件结尾。

# 输出

实现所有的进制转换，转换后的数右对齐到7位显示。如果转换后的数的位数太多，超过7位，则输出“ERROR”，也是右对齐到。

# 样例输入 复制

1111000  2 10
1111000  2 16
2102101  3 10
2102101  3 15
  12312  4  2
     1A 15  2
1234567 10 16
   ABCD 16 15

# 样例输出 复制

    120
     78
   1765
    7CA
  ERROR
  11001
 12D687
   D071

# 代码C语言：

#include<stdio.h>
#include<string.h>
#include<math.h>
char temp[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
char str2[10000];
int solve(char str[],int r1){
    int sum = 0;
    int len = strlen(str);
    int i;
    for(i = len-1;i >= 0;i--){
        if(str[i] >= '0' && str[i] <= '9'){
            sum = sum + (str[i]-'0')*pow(r1,len-i-1);
        }
        if(str[i] >= 'A' && str[i] <= 'F'){
            sum = sum + (str[i]-55)*pow(r1,len-i-1);
        }
    }
    return sum;
}
void solve2(int sum,int r2){
    int i = 0,j = 1;
    while(sum){
        str2[i] = temp[sum%r2];
        i++;
        sum /= r2;
    }
    str2[i] = '\0';
    int len = strlen(str2);
     
    for(j = 1;j <= 7 - len;j++){
        printf(" ");
    }if(len > 7){
        printf("  ERROR\n");
        return;
    }
    for(i = len-1;i >= 0;i--){
        printf("%c",str2[i]);
    }
    printf("\n");
}
int main(){
     
    char str[10000];
    int r1,r2;
    while(~scanf("%s %d %d",str,&r1,&r2)){
        solve2(solve(str,r1),r2);
    }
     
    return 0;
}

# 5007 回文数 (opens new window)

# 题目描述

如果一个数从左往右读和从右往左读都是一样的话，那么我们就称它是一个回文数。例如，75457就是一个回文数。 当然，这种性质要取决于这个数是在什么进制下。例如，17在十进制下不是一个回文数，但在二进制下（10001）则是一个回文数。 题目要求你来验证给定的数在2~16进制中的哪些进制下是否是回文数。

# 输入

输入文件包含了若干个十进制整数n，0 < n < 50000，每个整数占一行。0表示结束。

# 输出

如果整数i在某些进制下是回文数，则输出“Number i is palindrom in basis”，然后分别输出这些进制，其中i是给定的整数。如果在2~16进制下都不是回文数，则输出“Number i is not palindrom”。

# 样例输入 复制

17
19
0

# 样例输出 复制

Number 17 is palindrom in basis 2 4 16
Number 19 is not a palindrom

# 代码C语言：

#include<stdio.h>
#include<string.h>
char temp[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
void jinzhi(char str[],int n,int r){
     
    int i = 0;
    while(n){
        str[i++] = temp[n%r];
        n /= r;
    }   
}
int judge(char str[]){
    int i;
    int flag = 1;
    int len = strlen(str);
    for(i = 0;i <= len/2;i++){
 
        if(str[i] != str[len - i - 1]){
            flag = 0;
        }
    }
    return flag;
}
void solve(int n,int i,int count){
     
        if(count==0)
            printf("Number %d is palindrom in basis",n);
        printf(" %d",i);
     
}
int main(){
     
    int n;
    while(1){
        int flag = 0;
        int i;
        scanf("%d",&n);
        if(n==0) break;
        int count = 0;
        for(i = 2;i <= 16;i++){
            char str[100] = {'\0'};
            jinzhi(str,n,i);
            flag = judge(str);
                if(flag == 1){
                    solve(n,i,count);
                    count++;
            }
        }
        //printf("flag = %d\n",flag);
        if(count == 0){
            printf("Number %d is not a palindrom",n);
        }
        printf("\n");
    }
     
 
    return 0;
}

# 5101 十进制转换八进制 (opens new window)

# 题目描述

把一个十进制正整数转化成八进制。

# 输入

若干行，每行仅含一个十进制表示的正整数a(0 < a < 65536)。

# 输出

针对输入的每一行输出a的八进制表示。

# 样例输入 复制

9
8

# 样例输出 复制

11
10

# 代码C语言：

#include<stdio.h>
char num[] = {'0','1','2','3','4','5','6','7'};
int main(){
    
    int a;
    char str[10000];
    while(~scanf("%d",&a)){
        int temp = a;
        int i = 0,j;
        while(temp){
            str[i] = num[(temp%8)];
            temp /= 8;
            i++;
        }
        for(j = i - 1; j >= 0;j--){
            printf("%c",str[j]);
        }
        printf("\n");
    }
    
    return 0;
}

# 5102 Sky数 (opens new window)

# 题目描述

Sky从小喜欢奇特的东西，而且天生对数字特别敏感，一次偶然的机会，他发现了一个有趣的四位数2992，这个数，它的十进制数表示，其四位数字之和为2+9+9+2=22，它的十六进制数BB0，其四位数字之和也为22，同时它的十二进制数表示1894，其四位数字之和也为22，啊哈，真是巧啊。Sky非常喜欢这种四位数，由于他的发现，所以这里我们命名其为Sky数。但是要判断这样的数还是有点麻烦啊，那么现在请你帮忙来判断任何一个十进制的四位数，是不是Sky数吧。

# 输入

输入包括多个四位正整数，如果为0，则输入结束。

# 输出

若n为Sky数，则输出“#n is a Sky Number.”，否则输出“#n is not a Sky Number.”。每个结果占一行。注意：#n表示所读入的n值。

# 样例输入 复制

2992
1234
0

# 样例输出 复制

2992 is a Sky Number.
1234 is not a Sky Number.

# 代码C语言：

#include<stdio.h>
int main(){
    
    int num;
    while(~scanf("%d",&num)){
        if(num == 0) break;
        int sum10 = 0;
        int sum16 = 0;
        int sum12 = 0;
        int temp = num;
        int i,j;
        while(temp){
            sum10 += temp%10;
            temp /= 10;
        }
        temp = num;
        while(temp){
            sum16 += temp%16;
            temp /= 16;
        }
        temp = num;
        while(temp){
            sum12 += temp%12;
            temp /= 12;
        }
        if(sum10 == sum12 && sum10==sum16){
            printf("%d is a Sky Number.\n",num);
        }
        else{
            printf("%d is not a Sky Number.\n",num);
        }
    }
    
    return 0;
}

# 5111八进制转换十进制 (opens new window)

# 题目描述

把一个八进制正整数转化成十进制。

# 输入

输入有多行，每行仅含一个八进制表示的正整数a，a的十进制表示的范围是(0 < a < 65536)。

# 输出

一行，a的十进制表示。

# 样例输入 复制

11
10

# 样例输出 复制

9
8

# 代码C语言：

#include<stdio.h>
#include<string.h>
char str[10000];

int main(){
    while(~scanf("%s",str)){
         int sum = 0;
         int i = strlen(str);
         sum = 0;
         for(int j = 0;j < i;j++){
            sum = sum * 8 + (str[j]-'0');
        }
        printf("%d\n",sum);
    }
    return 0;
}

# 5112确定进制 (opens new window)

# 题目描述

6 * 9 = 42 对于十进制来说是错误的，但是对于13进制来说是正确的。即, 6(13) * 9(13) = 42(13)， 而 42(13) = 4 * 13^1 + 2* 13^0 = 54(10)。 你的任务是写一段程序读入三个整数p、q和r，然后确定一个进制B(2 <= B <= 16) 使得 p * q = r。如果 B有很多选择，输出最小的一个。例如：p = 11，q = 11，r = 121。则有 11(3) * 11(3) = 121(3) 因为 11(3) = 1 * 3^1 + 1 * 3^0 = 4(10) 和 121(3) = 1 * 3^2 + 2 * 3^1 + 1 * 3^0 = 16(10)。 对于进制10。有 11(10) * 11(10) = 121(10)。这种情况下，应该输出3。如果没有合适的进制，则输出0。

# 输入

输入有T组测试样例。 T在第一行给出。每一组测试样例占一行，包含三个整数p、q、r。p、q、r的所有位都是数字，并且1 <= p、q、r <= 1,000,000。

# 输出

对于每个测试输出样例一行。该行包含一个整数：即使得p * q = r成立的最小的B。如果没有合适的B，则输出 0。

# 样例输入 复制

3
6 9 42
11 11 121
2 2 2

# 样例输出 复制

13
3
0

# 代码C语言：

#include<stdio.h>
#include<string.h>
#include<math.h>

int main(){
    
    int t;
    scanf("%d",&t);
    char p[1000];
    char q[1000];
    char r[1000];
    int i,j,k,l;
    while(t--){
        scanf("%s %s %s",p,q,r);
        
        int len = strlen(r);
        int len1 = strlen(p);
        int len2 = strlen(q);
    
        
        for(i = 2;i <= 16;i++){
            long long sum = 0;
            long long sum1 = 0;
            long long sum2 = 0;
            for(k = len1-1; k >= 0;k--){
                sum1 += (p[k] - '0') * pow(i,len1 - k - 1);
                if((p[k] - '0') >= i) {
                    l  = -3;
                    k = -3;
                    j = -3;
                    break;
                }
            }
           
            for(l = len2-1; l >= 0;l--){
                sum2 += (q[l] - '0') * pow(i,len2 - l - 1);
                if((q[l] - '0') >= i) {
                    l  = -3;
                    k = -3;
                    j = -3;
                    break;
                }
            }
            for(j = len-1;j >= 0;j--){
                sum += (r[j] - '0') * pow(i,len - j - 1);
                if((r[j] - '0') >= i) {
                    l  = -3;
                    k = -3;
                    j = -3;
                    break;
                }
            }
            
            if(sum == sum1 * sum2 && l == -1 && j == -1 && k == -1){
                    printf("%d\n",i);
                    i = 17;
            }
            if(i == 16){
                printf("0\n");
            }
        }
    }
    
    return 0;
}

# 5201 二进制位 (opens new window)

# 题目描述

给定你一个十进制数n（0 < n < 1000），要求输出其二进制数。

# 输入

输入有多行，每行包括一个十进制的正整数n。

# 输出

输出对应的二进制数。

# 样例输入 复制

1
2
3

# 样例输出 复制

1
10
11

# 代码C语言：

#include<stdio.h>
int main(){
    int n;
    while(~scanf("%d",&n)){
        int str[1005] = {0};
        int i = 0;
        while(n){
            str[i++] = n % 2;
            n /= 2;
        }
        for(int j = i - 1;j >= 0;j--){
            printf("%d",str[j]);
        }
        printf("\n");
    }
}

# 5202 二进制转化为十六进制 (opens new window)

# 题目描述

输入一个2进制的数，要求输出该2进制数的16进制表示。在16进制的表示中，A-F表示10-15。

# 输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个以0和1组成的字符串，字符串长度至少是1，至多是10000。

# 输出

n行，每行输出对应一个输入。

# 样例输入 复制

2
100000
111

# 样例输出 复制

20
7

# 代码C语言：

#include<stdio.h>
#include<string.h>
#include<math.h>
char str2[10005];
int j = 0;
char temp[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G'};
void jinzhi(char str[]){
	int i;
	int len = strlen(str);
	int count = 0;
	int sum = 0;
	j = 0;
	for(i = len - 1;i >= 0;i--){
		sum += (int)((str[i] - '0') * pow(2,count));
		count++;
		if(count % 4 == 0){
			count = 0;
			str2[j++] = temp[sum];
			sum = 0;
		}
	}
	if(count!=0){
		str2[j++] = temp[sum];
	}
}
int main(){

	int n;
	int i = 0;
	scanf("%d",&n);
	while(n--){
		char str[10005] = {'\0'};
		scanf("%s",str);
		jinzhi(str);
		for(i = j - 1;i >= 0;i--){
			printf("%c",str2[i]);
		}
		printf("\n");
	}

	return 0;
}

# 5203 周易II (opens new window)

# 题目描述

有人说，中国古代的“周易”是二进制系统的起源，在该系统中，他们用“- -”表示1，“---”表示0。因此，二进制数字“011010”可以表述为“---\n- -\n- -\n---\n- -\n---\n”（符号“\n”表示换行）。现在的问题是如何把一个“周易”中的二进制转换为相应的十进制数？

# 输入

文件中包含多组测试数据。每个测试数据都是以一个数字k (0 < k <= 20)开始，表示这个数在二进制中的位数。接下来就是k行，就是字符串---或- -，第1位表示最高位。

# 输出

对于每组测试数据，输出对应的十进制数。

# 样例输入 复制

3
- -
- -
- -
3
---
---
---
6
---
- -
- -
---
- -
---

# 样例输出 复制

7
0
26

# 思考：

这道题有脏数据【确信】而且还有Linux系统很诡异的换行问题。

所以笔者推荐每一行都用fgets把换行符给读入了，不然可能产生不知名的错误。

# 代码C语言 代码一：

#include<stdio.h>
#include<string.h>
int main(){
     
    char str[1000][1000];
    int n;
    int i;
    char res[1000];
    while(~scanf("%d",&n)){
        int j = 0;
        getchar();
        getchar();
        for(i = 0;i < n;i++){
            gets(str[i]);
            if(strncmp(str[i],"- -",3)==0){
                res[j++] = '1';
            }
            if(strncmp(str[i],"---",3)==0){
                res[j++] = '0';
            }
        }//011010
        long long sum = 0;
        for(i = 0;i < j;i++){
            sum = sum * 2 + (res[i]-'0');
        }
        printf("%lld\n",sum);
    }
     
    return 0;
}

# 代码C语言 代码二：

#include<stdio.h> 
#include<string.h>
int str[10000];
long long solve(int n){
    long long sum = 0;
    for(int j = n;j >= 1;j--){
        sum += str[j] * pow(2,n - j);
    }
    return sum;
}
int main()
{
    char first[1000] = {'\0'};
    while(fgets(first,sizeof(first),stdin)){
        int k = first[0] - '0';
        for(int i = 1;i <= k;i++){
            char temp[1000] = {'\0'};
            fgets(temp,sizeof(temp),stdin);
            str[i] = temp[1] == '-' ? 0 : 1;
        }
        printf("%lld\n",solve(k));
    }
    return 0;
}

# 5204 二进制数 (opens new window)

# 题目描述

给定一个正整数n，要求输出对应的二进制数中所有数码“1”的位置。注意最低位为第0位。例如13的二进制形式为1101，因此数码1的位置为：0,2,3。

# 输入

输入文件中的第1行为一个正整数d，表示输入文件中测试数据的个数，1<=d<=10，接下来有d个测试数据。每个测试数据占一行，只有一个整数n，1<=n<= 106。

# 输出

输出包括d行，即对输入文件中的每个测试数据，输出一行。第i行，1 <= i <= d，以升序的顺序输出第i个测试数据中的整数的二进制形式中所有数码1的位置，位置之间有1个空格，最后一个位置后面没有空格。

# 样例输入 复制

2
13
127

# 样例输出 复制

0 2 3
0 1 2 3 4 5 6

# 代码C语言 代码一：

#include<stdio.h>
#include<string.h>
#include<math.h>
char str[10000];
char temp[] = {'0','1'};
int main(){
    int d;
    scanf("%d",&d);
    while(d--){
        int n;
        scanf("%d",&n);
        int i = 0,j = 0;
        while(n){
            str[i++] = temp[n%2];
            n /= 2;
        }
        for(j = 0;j < i;j++){
            if(str[j]=='1'){
                printf("%d ",j);
            }
        }
        printf("\n");
    }
	return 0;
}

# 代码C语言 代码二：

#include <stdio.h>
int main() {
    int d;
    scanf("%d", &d);
    while(d--) {
        int n;
        scanf("%d",&n);
        int first = 1;
        for(int i = 0;i < 31;i++){
            if((n & (1 << i)) != 0) {
                if(first){
                    printf("%d", i);
                    first = 0;
                }else{
                    printf(" %d", i);
                }
            }
        }
        printf("\n");
    }
    return 0;
}

# 5205 留下最少 (opens new window)

# 题目描述

给定一个基数b，和b进制下的两个非负整数p和m，计算p%m，并输出b进制下的结果。p%m的结果被定义为非负整数k，要求k是满足p=a * m + k中的最小值（a为某些整数）。

# 输入

输入包含多组测试数据。每个测试数据占一行，由3个无符号的整数构成，第一个整数为b，一个介于2到10之间的十进制数。第二个为p，可能由1000位的0到b-1构成。第三位是m，由9位0到b-1构成。 最后一个测试数据为0，表示输入结束。

# 输出

对应每组测试数据，要求输出一行b进制下的p%m。

# 样例输入 复制

2 1100 101
10 123456789123456789123456789 1000
0

# 样例输出 复制

10
789

# 思路：

一个任意进制的数，对x取余的结果 等于 其各个数位上的数对x取余的结果的和 再对x取余。

即 对于任何整数 $a$, $b$, $m$，我们有 $(a + b) % m = ((a % m) + (b % m)) % m$

比如 $123456789$，即 $110^8 + 210^7 + 310^6 + 410^5 + 510^4 + 610^3 + 710^2 + 810^1 + 9*10^0$

$(1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9) % 10 = 45 % 10 = 5$。

所以这道题我们求的虽然是$p % m$，实际上就是：如果一个数$p$在任意进制下表示为$d_1d_2d_3...d_n$，那么$p%m = ((d_1%m) + (d_2%m) + ... + (d_n%m)) % m$

然后具体请看代码~

# 代码C语言：

#include<stdio.h>
#include<string.h>

int main(){
    int b;
    char p[1005], m[10];
    while(scanf("%d", &b) != EOF && b) {
        scanf("%s %s",p,m);
        long long mx = 0;
        int len_m = strlen(m);
        //求m的值
        for(int i = 0;i < len_m;i++)
            mx = mx * b + m[i] - '0';
        long long px = 0;
        int len_p = strlen(p);
        //用模运算求p的值
        for(int i = 0; i < len_p; i++){
            px = px * b + p[i] - '0';
            px %= mx;
        }
        //特判0
        if(px == 0)
            printf("0\n");
        else{
            char ans[1005];
            int len = 0;
            //进制转换成b进制
            while(px > 0){
                ans[len++] = px % b + '0';
                px /= b;
            }
            for(int i = len - 1;i >= 0;i--)
                printf("%c", ans[i]);
            printf("\n");
        }
    }
    return 0;
}

# 5206 进制转换 (opens new window)

# 题目描述

编写程序，实现将一个数从一种进制转换到另一种进制。在这些进制中，可以出现的数码有62个：{0-9,A-Z,a-z}。

# 输入

输入文件的第1行是一个正整数N，表示测试数据的个数，接下来有N行，每行的格式为：输入数据的进制（用十进制表示），输出数据的进制（用十进制表示），最后一个是用输入数据的进制所表示的数。输入/输出数据的进制范围是2 ~ 62，也就是说A ~ Z相当于十进制中的10 ~ 35，a ~ z相当于十进制中的36 ~ 61。

# 输出

对每个测试数据，程序输出3行，第1行是输入数据的进制，空格，然后是在该进制下的输入数据；第2行是输出数据的进制，空格，然后是在该进制下的输出数据；第3行为空行。

# 样例输入 复制

8
62 2 abcdefghiz
10 16 1234567890123456789012345678901234567890
16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 23 333YMHOUE8JPLT7OX6K9FYCQ8A
23 49 946B9AA02MI37E3D3MMJ4G7BL2F05
49 61 1VbDkSIMJL3JjRgAdlUfcaWj
61 5 dl9MDSWqwHjDnToKcsWE1S
5 10 42104444441001414401221302402201233340311104212022133030

# 样例输出 复制

62 abcdefghiz
2 11011100000100010111110010010110011111001001100011010010001

10 1234567890123456789012345678901234567890
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 333YMHOUE8JPLT7OX6K9FYCQ8A

35 333YMHOUE8JPLT7OX6K9FYCQ8A
23 946B9AA02MI37E3D3MMJ4G7BL2F05

23 946B9AA02MI37E3D3MMJ4G7BL2F05
49 1VbDkSIMJL3JjRgAdlUfcaWj

49 1VbDkSIMJL3JjRgAdlUfcaWj
61 dl9MDSWqwHjDnToKcsWE1S

61 dl9MDSWqwHjDnToKcsWE1S
5 42104444441001414401221302402201233340311104212022133030

5 42104444441001414401221302402201233340311104212022133030
10 1234567890123456789012345678901234567890

# 代码C语言：

#include <stdio.h>
#include <string.h>

int main() {
    int t;
    scanf("%d", &t);
    while(t--){
        int a, b;
        char c[100],d[100];
        scanf("%d %d %s",&a,&b,c);
        int arr[100] = {0},res[100] = {0};
        int arr_size = 0;
        int len_c = strlen(c);
        
        for(int i = len_c - 1;i >=0;i--){//反转得到数组
            if(c[i] >='0' && c[i] <='9') arr[arr_size++] = c[i] - '0';
            if(c[i] >='A' && c[i] <='Z') arr[arr_size++] = c[i] - 'A' + 10;
            if(c[i] >='a' && c[i] <= 'z') arr[arr_size++] = c[i] - 'a' + 36;
        }
        int res_size = 0;
        
        while(arr_size){ 
            int r = 0;
            //进制转换
            for(int i = arr_size - 1;i >=0;i--){
                arr[i] += r * a;
                r = arr[i] % b;
                arr[i] /= b;
            }
            res[res_size++] = r;//每次将余数加入到数组中
            while(arr_size && arr[arr_size - 1] == 0) arr_size--;//去除前导0
        }
        
        int d_index = 0;
        //把数字转换成进制的字符
        for(int i = res_size - 1;i >= 0;i--){
            if(res[i] >= 0 && res[i] <= 9) d[d_index++] = res[i] + '0';
            if(res[i] >= 10 && res[i] <= 35) d[d_index++] = res[i] + 'A' - 10;
            if(res[i] >= 36) d[d_index++] = res[i] + 'a' - 36;
        }
        d[d_index] = '\0';
        
        printf("%d %s\n",a,c);
        printf("%d %s\n\n",b,d);
    }
    return 0;
}

# 总结

  1. 这套题都是进制转换，大多数题目考察的内容都是一致的，本质上就是进制转换，善用短除法处理，把余数存储，就可以得到不同的进制。
  2. 部分题目会涉及到字符串的使用，还有像周易Ⅱ该题会出现字符处理的情况，需要用fgets整行读入为好。

← NENUOJ 之 算法1第6章 →