XTU-OJ 1328-数码和

题目描述

一个10进制数n在2∼16进制下可以得到的不同的数码和，求在这些数码和中出现次数最多的数码和。 比如20，

进制2345678910111213141516数码10100202110403226242220191817161514数码和2424586421098765

其中数码和2和4分别出现了3次，为最多出现次数。

输入

第一行是一个整数T(1≤T≤1000)，表示样例的个数。 以后每行一个整数n(16≤n≤109)。

输出

依次输出各样例的结果，每个样例输出的第一行是最多的次数。
然后，按数码和值的升序依次输出最多次的数码和，每行输出一种。
每行先输出这个数码和的值，然后按进制的顺序输出出现这个数码和的进制，每个值之间用一个空格隔开。

样例输入

3
17
20
1000000000

样例输出

4
5 3 5 7 13
3
2 2 4 10
4 3 5 9
2
34 7 8

 解题思路： 按步骤来，先把十进制数 n 转换成 2->16 进制的数的 数码和。在另外开一个标记数组 books，记录 该数码和 出现的次数。（n最大是 1e9，各进制下的数码和最大也就100以内，我这里随便开了个长度 135，需要严谨点的可以自己去估一下），同时记录出现的最大次数。

然后依次输出：最大次数、数码和、对应进制。

AC代码：

#include <stdio.h>
#include <string.h>int T,n,n0,i,j;
int maxNum;
int record[20],books[135];    // record[i][0] 保存 进制i的 数码和
void exchange()
{// 初始化maxNum = 0;memset(record,0,sizeof(record));memset(books,0,sizeof(books));// 2->16 进制转换for ( i = 2; i <= 16; i ++){//   求各进制的 数码和n0 = n;while ( n0 ){record[i] += n0%i;n0 /= i;}books[record[i]] ++;if (maxNum < books[record[i]])      // 记录出现最多的 次数maxNum = books[record[i]];}
}
int main()
{scanf("%d",&T);while ( T --){scanf("%d",&n);exchange();printf("%d\n",maxNum);for (i = 1; i < 135; i ++){if (books[i] == maxNum){printf("%d",i);                 // 输出 数码和for (j = 2; j <= 16; j ++)if (record[j] == i)printf(" %d",j);        // 输出 进制puts("");}}}return 0;
}