PAT 1010. PAT-1010 -Radix
原题链接
困难
这个题目真的拿满分不容易!!!
需要注意的地方是: 题目只给出了36个数, 但是进制却是可以非常大(需要用long long来存), 同时中间的计算结果会超过long long的范围 需要使用double来计算, 如果对double不熟悉的话, 自然不能自信地完成这个题目, 代码如下:
代码:
/*
* Author: Apprentice_lb
* Created Time: 2022/2/19 13:17:39
* File Name: pat.cpp
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
const int N = 20;
const double eps = 1e-4;
char n1[N], n2[N], n[N];
int tag, rad;
long long num;
inline int to(char c){
if(isdigit(c)) return (c - '0');
else return (c - 'a' + 10);
}
double count(char a[N], double r){
double res = 0;
double tmpr = 1;
int len = strlen(a);
for(int i = len - 1; i >= 0; i--){
double val = to(a[i]);
res += (val * tmpr);
tmpr *= r;
}
return res;
}
int main() {
scanf("%s%s%d%d", n1, n2, &tag, &rad);
int len = strlen(n2);
if(tag == 1){
memcpy(n, n2, sizeof n2);
num = count(n1, rad);
}
else if(tag == 2){
memcpy(n, n1, sizeof n1);
num = count(n2, rad);
}
else assert(0);
int i = 0;
for(int j = 0; j < strlen(n); j++){
i = max(i, to(n[j]));
}
long long l = i + 1, r = num + 1;
int tim = 0;
while(l < r){
tim++;
long long mid = (l + r) / 2;
double tmp = count(n ,mid);
if(tmp >= (double)num || abs(tmp - (double)num) < eps) r = mid;
else l = mid + 1;
}
if(l != r) assert(l >= r);
if((long long)count(n, l) == num) printf("%d\n", l);
else puts("Impossible");
return 0;
}