【TSOJ课程】1119 确定进制

课程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为止,然后从下往上读余数。
【TSOJ课程】1119 确定进制
如图,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;
}

上一篇:jquery实现 数字变化效果


下一篇:linux下,一些关于动态库的问题: