pat甲級1010 Radix(二分検索)
1299 ワード
问题を作る+コードを见る2 h...デバグ30分
#include
#include
#include
#include
#include
using namespace std;
long long convert(string n, long long radix) {
long long _n = 0;
int temp=0, index = 0;
for (auto c = n.rbegin(); c != n.rend(); c++) {
temp = isdigit(*c) ? *c - '0' : *c - 'a' + 10;
_n +=temp* pow( radix,index++);
}
return _n;
}
long long find_radix(string n,long long num) {
char it = *max_element(n.begin(), n.end());
long long low = (isdigit(it) ? it - '0': it - 'a' + 10) + 1;
long long high = max(num, low);
while (low <= high) {
long long mid = (low + high) / 2;
long long t = convert(n, mid);
if (t<0||t > num) high = mid - 1;
else if (t == num) return mid;
else low = mid + 1;
}
return -1;
}
int main() {
string n1, n2;
long long tag=0, radix=0, result_radix=0;
cin >> n1 >> n2 >> tag >> radix;
if (tag == 1)
result_radix = find_radix(n2, convert(n1, radix));
else
result_radix = find_radix(n1, convert(n2, radix));
if (result_radix != -1)
cout << result_radix << endl;
else
cout << "Impossible
";
return 0;
system("pause");
}