课程29_14 1119 确定进制
题目:
题目描述:
6 × 9 = 42 对于十进制来说是错误的,但是对于 13 进制来说是正确的。即,6(13) × 9(13) = 42(13), 而 42(13) = 4 × 13 + 2 = 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 × 31 + 1 × 30 = 4(10) 且 121(3) = 1 × 32 + 2 × 31 + 1 × 30 = 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
解析:
很常规的枚举题,主要考察的是进制转换的原理。
因为题目给出的数据是“未知进制”(也就是不等于10进制的)的数字,所以我们只需要知道X进制转10进制怎么做就可以了。
任意进制转10进制的公式:
num10 = d0 x D0 + d1 x D1 + d2 x D2 + …… + dn x Dn
其中dn指的是从右往左的第n+1位,如d0是个位,d1是十位等等。D指的是数字的进制,如5进制转10进制时,D为5。
补充知识
10进制转任意进制的方法是辗转相除法
方法就是把n先除以D,余数写在左侧,商写在下方,然后继续,直到商小于D为止,然后从下往上读余数。
如图,2018÷16=126……2,把2写在左侧,然后126÷16=7……14,把14写在左侧。此时7已经小于16了,停下来,从下往上读:7、14、2,其中14我们写作E,所以2018(10)=7E2(16)。括号表示这个数字的进制。
解题:
参考代码:
// TSOJ-1119 确定进制
#include <stdio.h>
#include <math.h>
int to10(int, int);
int main()
{
int T;
int p,q,r,tp,tq,tr;
int i;
scanf("%d",&T);
for(;T--;){
scanf("%d %d %d",&p,&q,&r);
for(i=2; i<17; i++){
tp = to10(p,i);
if(tp==-1)
continue;
tq = to10(q,i);
if(tq==-1)
continue;
tr = to10(r,i);
if(tr==-1)
continue;
if(tp*tq==tr){
break;
}else{ // tp*tq>tr
continue;
}
}
if(i>=17){
printf("0\n");
}else{
printf("%d\n",i);
}
}
return 0;
}
int to10(int num, int base)
{
int ret=0,dig=0,temp;
while(num>0){
temp = num%10;
if(temp>=base){
return -1; // 无效
}
ret += temp*pow(base,dig++);
num /= 10;
}
return ret;
}
其实还有一种优化方法,是我无意间算出来的。就是直接把数字当成10进制算,pq r,如果关系是pq>r,那么说明进制是10以上的,否则就是10以下的。
并且,如果进制是10以上的,我们先把他当成D进制转化为tp、tq、tr。很显然如果tptq=tr就找到答案了,但是如果tptq>tr,说明再往上找也找不到了。这个证明还挺绕的,如果大家有兴趣可以自己试试看去证明。
这种优化方法的作用是,不需要知道进制的限制。传统的方法是枚举完2~16所有进制,如果没有一个满足条件,就说明没有,这种方法需要我们知道进制的范围。而现在说的优化算法不需要知道,它会在tp*tq>tr的时候自动终止查找。
// TSOJ-1119 确定进制
#include <stdio.h>
#include <math.h>
int to10(int, int);
int main()
{
int T;
int p,q,r,tp,tq,tr;
int i;
scanf("%d",&T);
for(;T--;){
scanf("%d %d %d",&p,&q,&r);
if(p*q>r){
// 10+进制
for(i=11;i<17;i++){
tp = to10(p,i);
tq = to10(q,i);
tr = to10(r,i);
if(tp*tq==tr){
break;
}else if(tp*tq<tr){ // 再往后也没有了
tr = -1;
break;
}else{ // tp*tq>tr
continue;
}
}
if(tr==-1 || i>=17){
// i>=17是题目的要求,如果题目不给进制范围的话,这里值判断tr是否等于-1
printf("0\n");
}else{ // tr!=-1 and i<17
printf("%d\n",i);
}
}else{
// 2~10进制
for(i=2;i<=10;i++){
tp = to10(p,i);
if(tp==-1)
continue;
tq = to10(q,i);
if(tq==-1)
continue;
tr = to10(r,i);
if(tr==-1)
continue;
if(tp*tq==tr){
break;
}else if(tp*tq<tr){
tr = -1;
break;
}else{ // tp*tq>tr
continue;
}
}
if(tr==-1 || i>10){
// 没有
printf("0\n");
}else{ // tr!=-1 and i<=10
printf("%d\n",i);
}
}
}
return 0;
}
int to10(int num, int base)
{
int ret=0,dig=0,temp;
while(num>0){
temp = num%10;
if(temp>=base){
return -1; // 无效
}
ret += temp*pow(base,dig++);
num /= 10;
}
return ret;
}