欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PAT甲级——A1010 Radix

程序员文章站 2022-03-13 18:21:11
...

题目

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers N​1​​ and N​2​​, your task is to find the radix of one number while that of the other is given.

Input Specification:

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:

N1 N2 tag radix

Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.

Output Specification:

For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.

Sample Input 1:

6 110 1 10

Sample Output 1:

2

Sample Input 2:

1 ab 1 2

Sample Output 2:

Impossible

Solution:

题意:
根据给出的数,求出另一个数的满足要求的进制

题解:
这题不难,主要是要考虑数据溢出的问题(巨恶心,搞了我半天)
记得要使用二分法去寻找匹配的进制(这个一超时就能想起)

Code


#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
string n, m;
int t, k;
//根据进制计算十进制数值
long long calValue(string x, long long r)
{
	if (r == 10)return atoi(x.c_str());
	long long sum = 0, k = 1;
	for (int i = x.length()-1;i>=0;--i)
	{
		sum += k * (isalpha(x[i]) ? (x[i] - 'a' + 10) : (x[i] - '0'));
		k *= r;
	}
	return sum;
}

long long calRadix(string x)
{
	//首先计算x中的最大数值
	int maxV = 0;
	for (auto a : x)
		maxV = max(maxV, isalpha(a) ? (a - 'a' + 10) : (a - '0'));
	long long nV = calValue(n, k);//计算n的十进制数
	long long L = maxV + 1, R = nV > 36 ? nV : 36, mid;//一定得使用二分法
	while (L <= R)
	{
		mid = L + (R - L) / 2;
		long long mV = calValue(x, mid);
		if (nV == mV)
			return mid;
		if (mV > nV || mV<0)//mV<0表示溢出,进制太大了
			R = mid - 1;
		else
			L = mid + 1;
	}
	return -1;
}
int main()
{
	cin >> n >> m >> t >> k;
	if (t == 2)
		swap(n, m);//记住n为已知的进制数
	long long res = calRadix(m);
	if(res>-1)
		cout << res << endl;
	else
		printf("Impossible");
	return 0;
}
相关标签: 进制