1010 Radix
题意
给定两个数，并告诉其中一个数的进制数，然后判断是否存在一个进制使得两个数相等
思路
这题题目很好理解,就是做起来真难受,各种部分正确
总体思路就是使用二分法找进制,按照进制转换成数字.
其中二分的下限是所有进制数中最大数加1，上限是此数本身。
要考虑数位益处的问题，溢出后其数符号位为负
源码
line_number: true1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include<iostream>
#include<cctype>
#include<algorithm>
#include<cmath>
using namespace std;
long long str2RadixNum(string strNum, long long llRadix)
{
long long llNum = 0;
for(auto pT = strNum.begin(); pT != strNum.end(); pT++)
{
llNum = llNum * llRadix + (isdigit(*pT) ? (*pT - '0') : (*pT - 'a' + 10));
}
return llNum;
}
long long findNumRadix(string strNum, long long llTagNum)
{
long long strMaxChar = *max_element(strNum.begin(), strNum.end());
long long llLow = (isdigit(strMaxChar) ? strMaxChar - '0' : strMaxChar - 'a' + 10) + 1;
long long llHigh = max(llLow,llTagNum);
while(llLow <= llHigh)
{
long long llMedium = (llLow + llHigh) / 2;
long long llMediumRadixNum = str2RadixNum(strNum, llMedium);
if(llMediumRadixNum < 0 || llMediumRadixNum > llTagNum)
{
llHigh = llMedium - 1;
}
else if(llMediumRadixNum < llTagNum)
{
llLow = llMedium + 1;
}
else
{
return llMedium;
}
}
return -1;
}
int main()
{
string strN1;
string strN2;
int iTag;
long long llRadix;
while(cin>> strN1 >> strN2 >> iTag >> llRadix)
{
long long llTagNum = iTag == 1 ? str2RadixNum(strN1, llRadix) : str2RadixNum(strN2, llRadix);
long long llResult = iTag == 1 ? findNumRadix(strN2, llTagNum) : findNumRadix(strN1, llTagNum);
llResult == -1 ? cout << "Impossible" <<endl : cout<< llResult <<endl;
}
return 0;
}
|