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 N1 and N2, your task is to find
the radix of one number while that of the other is given.
[编程题]Radix (25)
- 热度指数：7057 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
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.
输出描述:
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.
示例1
输入
6 110 1 10
输出
2<br/>Sample Input 2:<br/>1 ab 1 2<br/>Sample Output 2:<br/>Impossible
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int map[128];
void init(){ //初始化，将字符影射成数字
for(char c = '0'; c <= '9'; c++)
map[c] = c - '0';
for(char c = 'a'; c <= 'z'; c++)
map[c] = c - 'a' + 10;
}
long long toten(char a[], long long radix){ //化为十进制
long long ans=0;
int len=strlen(a);
for(int i=0;i<len;i++)
ans=ans*radix+map[a[i]]; //溢出
if(ans<0) return -1;
return ans;
}
int find_largest_didit(char s[]){ //求最大的数位
int max=-1,len=strlen(s);
for(int i=0;i<len;i++){
if(map[s[i]]>max)
max=map[s[i]];
}
return max+1; //数位最大为max，进制位为max+1作为下界
}
int main(){
init();
char s1[15],s2[15];int tag,radix;
cin>>s1>>s2>>tag>>radix;
if(tag==2)
swap(s1,s2);
long long m=toten(s1,radix),n;
long long left=find_largest_didit(s2),mid;
long long right=max(left,m)+1; //进制位上界
while(left<=right){
mid=(left+right)/2;
n=toten(s2,mid);
if(n==m){
cout<<mid;
return 0;
}
else if(n==-1||n>m) right=mid-1; //s2的mid进制溢出或者大于s1的十进制
else left=mid+1;
}
cout<<"Impossible";
return 0;
}
发表于 2018-02-02 02:13:53
回复(0)
Java解法，网上大部分解法还是用cpp写的。
关键点就是要用BigInteger，用Long和int都会越界（PAT中的测试样例比较严格）
import java.math.BigInteger; import java.util.Scanner; /** * 1010. Radix (25) * @author Jacob * 关键点：用BigInteger代替Long */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String n1 = sc.next(), n2 = sc.next(); int tag = sc.nextInt(), radix = sc.nextInt(); // 方便计算，把n1当做已知进制，n2未知 if (tag == 2) { String tmp = n1; n1 = n2; n2 = tmp; } //将n1转成数字 BigInteger num1 = str2Num(n1, radix); //找出num1中的最大数字 BigInteger low=findBiggest(n2); BigInteger minRadix=BigInteger.ZERO; BigInteger left=low.add(BigInteger.ONE); BigInteger right=num1.max(BigInteger.valueOf(50)).add(BigInteger.ONE); while(left.compareTo(right)!=1){ //二分法，mid为left+(right-left)/2；BigInteger的写法与一般写法不同 BigInteger mid=left.add(right).divide(BigInteger.valueOf(2)); BigInteger tmpValue=BigInteger.ZERO; //设置标志，记录tmpValue与num1的大小关系 int flag=-1; for(int i=0;i<n2.length();i++){ tmpValue=tmpValue.multiply(mid).add(char2Num(n2.charAt(i))); if(tmpValue.compareTo(num1)==1){ flag=1; break; }else if(tmpValue.compareTo(num1)==0){ flag=0; break; } } //根据flag判断当前mid与midValue大小关系 if(flag==1) right=mid.subtract(BigInteger.ONE); else if(flag==-1) left=mid.add(BigInteger.ONE); else{ minRadix=mid; right=mid.subtract(BigInteger.ONE); } } if(minRadix.equals(BigInteger.ZERO)) System.out.println("Impossible"); else System.out.println(minRadix); sc.close(); } /* * 找出字符串中字符表示的最大数字 */ private static BigInteger findBiggest(String str) { BigInteger max=BigInteger.ZERO; for(int i=0;i<str.length();i++){ if(max.compareTo(char2Num(str.charAt(i)))==-1) max=char2Num(str.charAt(i)); } return max; } /* * 将输入字符串转化为BigInteger */ private static BigInteger str2Num(String str, int radix) { BigInteger value=BigInteger.ZERO; for(int i=0;i<str.length();i++){ value=value.multiply(BigInteger.valueOf(radix)).add(char2Num(str.charAt(i))); } return value; } /* * 字符转BigInteger */ private static BigInteger char2Num(Character c) { BigInteger value; if (c >= '0' && c <= '9') value = BigInteger.valueOf(c - '0'); else value = BigInteger.valueOf(c - 'a' + 10); return value; } }
编辑于 2017-08-28 14:09:24
回复(0)
//pat和牛客都过了
#include<iostream>
#include<cstring>
using namespace std;
int main() {
char cs1[11];
char cs2[11];
int tag;
int radix;
cin >> cs1 >> cs2 >> tag >> radix;
if (tag == 2) {
char cstmp[11];
strcpy(cstmp, cs1);
strcpy(cs1, cs2);
strcpy(cs2, cstmp);
}
//这个没有加上之前始终过不了pat的case 10
if (strcmp(cs1, cs2) == 0){
cout << radix << endl;
return 0;
}
int len = strlen(cs1);
long long value = 0;
for (int i = 0; i < len; i++) {
char c = cs1[i];
long long digit;
if (c >= 'a') {
digit = c - 87;
}
else {
digit = c - 48;
}
value = value * radix + digit;
if (value < 0) {
cout << "Impossible" << endl;
//system("pause");
return 0;
}
}
int len2 = strlen(cs2);
int *n2;
int maxDigit = 0;
n2 = new int[len2];
for (int i = 0; i < len2; i++) {
char c = cs2[i];
if (c >= 'a') {
n2[i] = c - 87;
}
else {
n2[i] = c - 48;
}
if (n2[i] > maxDigit) {
maxDigit = n2[i];
}
}
long long minResRadixDL = maxDigit + 1;
long long curvalue = 0;
long long l = minResRadixDL;
long long h = value > l ? value : l;
while (h >= l) {
long long m = (h + l) / 2;
curvalue = 0;
for (int j = 0; j < len2; j++) {
curvalue = curvalue * m + n2[j];
//这步很关键，防止溢出
if (curvalue > value) {
h = m - 1;
break;
}
else if (curvalue < 0) {
cout << "Impossible" << endl;
//system("pause");
return 0;
}
}
if (curvalue == value) {
cout << m << endl;
//system("pause");
return 0;
}
if (curvalue < value) {
l = m + 1;
}
//cout << "curvalue=" << curvalue << endl;
}
cout << "Impossible" << endl;
//system("pause");
return 0;
}
发表于 2017-04-05 16:27:28
回复(1)
#include <bits/stdc++.h>
using namespace std;
char a[3][11];
typedef long long LL;
LL convertNum10(char ch[], LL base, LL Inf){//将base进制转化为十进制
LL ans = 0;
int len = strlen(ch);
for(int i = 0; i < len; i++){
ans = ans*base + (isdigit(ch[i]) ? ch[i]-'0':ch[i]-'a'+10);
if(ans<0||ans>Inf) return -1;//剪枝,计算过程中一旦超过，即返回
}
return ans;
}
LL find_radix(LL x, char ch[]){//求ch在何种进制下等于x,进制有单调性可二分
int len = strlen(ch);
char maxc = *max_element(ch,ch+len);//寻找ch中的最大值
LL l = (isdigit(maxc) ? maxc-'0':maxc-'a'+10) + 1;//二分下界
LL r = max(x,l);
while(l <= r){
LL mid = (l+r) >> 1,y = convertNum10(ch,mid,x);
if(y<0||y>x) r = mid-1;//溢出
else if(y==x) return mid;
else l = mid+1;
}
return -1;//查找失败
}
int main(){
int tag,flag = 0;
LL x,radix;
scanf("%s %s %d %lld",a[1],a[2],&tag,&radix);
x = convertNum10(a[tag],radix,(1LL<<63)-1);
LL ans = find_radix(x,a[3-tag]);
if(ans==-1) printf("Impossible\n");
else printf("%lld\n",ans);
return 0;
}
发表于 2019-05-05 16:19:52
回复(0)
发表于 2018-07-27 13:58:06
回复(0)
/*向一楼学习！//牛客，pat双通过
第一：转化为十进制时，形参p(即radix)取long long，
否则无法通过：10 aaaaaaaaaa 2 15
第二：转化为十进制时，溢出表示p选取过大*/
#include <iostream>
#include<algorithm>
#include<string>
using namespace std;
long long p2dec(string n,long long p)//转化为十进制
{
int temp;
long long sum=0;
for(int i=0;i<n.size();i++)
{
if(n[i]>='0'&&n[i]<='9')
temp=n[i]-'0';
else if(n[i]>='a'&&n[i]<='z')
temp=n[i]-'a'+10;
sum=sum*p+temp;
}
if(sum<0) //溢出
return -1;
return sum;
}
int find_lar(string n)
{
int temp,m=-1;
for(int i=0;i<n.size();i++)
{
if(n[i]>='0'&&n[i]<='9')
temp=n[i]-'0';
else if(n[i]>='a'&&n[i]<='z')
temp=n[i]-'a'+10;
m=max(m,temp);
}
return m+1; //"A digit is less than its radix "
}
int main()
{
int tag,rad;
string n1,n2;
long long n_1,n_2,mid,left,right;
cin>>n1>>n2>>tag>>rad;
if(tag==2)
swap(n1,n2);
n_1=p2dec(n1,rad);
left=find_lar(n2);
right=max(n_1,left)+1;
while(left<=right)//采用二分法
{
mid=(left+right)/2;
n_2=p2dec(n2,mid);
if(n_2==n_1)
{
cout<<mid<<endl;
return 0;
}
else if(n_1<n_2||n_2==-1)
right=mid-1;
else
left=mid+1;
}
cout<<"Impossible"<<endl;
return 0;
}
编辑于 2018-03-03 10:02:14
回复(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=LLONG_MAX;
LL Map[128];
string N1,N2;
LL tag,radix;
void Initial() {
for(char c='0'; c<='9'; c++) {
Map[c]=c-'0';
}
for(char c='a'; c<='z'; c++) {
Map[c]=c-'a'+10;
}
}
LL change10(string N,LL radix,LL r){
LL answer=0,n=N.size();
for(int i=0;i<n;i++){
answer=answer*radix+Map[N[i]];
if(answer<0||answer>r){
return -1;
}
}
return answer;
}
LL cmp(string N2,LL radix,LL r){
LL num=change10(N2,radix,r);
if(num==-1) return 1;
else if(r>num) return -1;
else if(r==num) return 0;
else return 1;
}
LL Binary(string N2,LL L,LL R,LL r){
while(L<=R){
LL mid=(L+R)/2;
int a=cmp(N2,mid,r);
if(a==1){
R=mid-1;
}else if(a==0){
return mid;
}else{
L=mid+1;
}
}
return -1;
}
LL getL(string N2){
LL answer=-1,n=N2.size();
for(int i=0;i<n;i++){
if(answer<Map[N2[i]]){
answer=Map[N2[i]];
}
}
return answer+1;
}
int main() {
ios::sync_with_stdio(0);
Initial();
cin>>N1>>N2>>tag>>radix;
if(tag==2) {
swap(N1,N2);
}
LL r=change10(N1,radix,INF);
LL L=getL(N2);
LL R=max(L,r)+1;
LL answer=Binary(N2,L,R,r);
if(answer==-1) {
cout<<"Impossible"<<endl;
} else {
cout<<answer<<endl;
}
return 0;
}
发表于 2022-11-13 11:00:02
回复(1)
//1)选用LL 2）二分查找 3）上限n1的十进制数+1，下限n2的single digit最大值（2~35）+1
#include<iostream>
(720)#include<string>
#include<algorithm>
(831)#define LL long long int
using namespace std;
char findmax(string s)
{
char c=s[0];
for(int i=1;i<s.size();i++)
if(c<s[i]) c=s[i];
return c;
}
LL changebasetodecimal(string s,LL redix)
{
LL k=0;
int i=0;
do
{
if(s[i]>='0'&&s[i]<='9')
k=k*redix+(s[i]-'0');
else
k=k*redix+(s[i]-'a'+10);
if(k<0)
return -1;
i++;
}while(i<s.size());
return k;
}
int main()
{
string n1,n2;
int tag,redix;
cin>>n1>>n2>>tag>>redix;
if(tag==2)
swap(n1,n2);
LL k1=changebasetodecimal(n1,redix);
char c=findmax(n2);
int r=0;
if(c>'0'&&c<'9')
r=c-'0';
else
r=c-'a'+10;
LL low=r+1,high=k1+1;
while(low<=high)
{
LL mid=(low+high)/2;
LL k2=changebasetodecimal(n2,mid);
if(k2==k1)
{
cout<<mid<<endl;
return 0;
}
else if(k2>k1||k2==-1)
high=mid-1;
else if(k2<k1)
low=mid+1;
}
cout<<"Impossible"<<endl;
return 0;
}
发表于 2020-03-30 13:21:04
回复(0)
# 今天才知道二分法的强大，题目的用例化简之后居然超过了2 的50次幂，真是丧心病狂！
import sys
a = input().split(' ')
b = a[int(a[2]) - 1]
m = 0;p = 36;q = pow(2,60);f = 0
j = len(b) - 1
for i in b:
if i <= 'z' and i >= 'a':
i = ord(i) - 87
m += int(i) * (int(a[3]) ** j)
j -= 1
def jian(x):
n = 0
j = len(a[2 -int(a[2])]) - 1
for i in a[2 -int(a[2])]:
if i <= 'z' and i >= 'a':
i = ord(i) - 87
n += int(i) * (x ** j)
j -= 1
return n
while f == 0:
n = jian(p)
if m == n:
print(p);sys.exit(0)
elif m < n:
f = 1
else:
f = 2
while f == 1:
if n > m:
p -= 1
elif n < m&nbs***bsp;p < 2 :
print('Impossible');sys.exit(0)
else:
print(p);sys.exit(0)
n = jian(p)
while f == 2:
if m < n:
p += q
elif m == a:
print(p);sys.exit(0)
else:
break
n = jian(p)
while f:
q = (q + 1) // 2
if n > m:
p -= q
elif n < m:
p += q
else:
print(p);sys.exit(0)
if q == 1:
f -= 1
n = jian(p)
print('Impossible')
发表于 2020-01-28 15:56:58
回复(0)
//几乎把所有坑都挖了一遍
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
//1010 Radix
//给出2个整数，和其中一个的进制，求另一个进制radix使两数相等
//如6(10)=110(2)，已知6 110 1 10，
//代表第一个数字6的进制为10，求110的进制使6(10)=110(radix)
//由题目可知数字部分不超过36
int num[36];
int to_num(char c) {
if (c >= 'a' && c <= 'z') {
return num[c - 'a' + 10];
}
else if (c >= '0' && c <= '9') {
return num[c - '0'];
}
else {
return -1;
}
}
int main() {
string a, b;
int tag, r;
unsigned long long t1 = 0, t2 = 0;
cin >> a >> b >> tag >> r;
if (a == b) { cout << r; return 0; } //pat.10
//初始化
for (int i = 0; i<36; ++i) num[i] = i;
//保证r指向a的进制，求b的进制
if (tag == 2) {
a.swap(b);
}
int len = a.size();
t1 = 0;
for (int i = 0; i < len; ++i) {
//t1 += to_num(a[i])*pow((double)r, double(len - i - 1));
//从别人那里学到一个不用pow()的计算方法
t1 = t1 * r + to_num(a[i]); //神奇又简便！
}
len = b.size();
if (len == 1) { //pat.1 长度为1的时候不能用下面的pow计算lo和hi
if (to_num(b[0]) == t1) {
cout << t1 + 1;
return 0;
}
else {
cout << "Impossible";
return 0;
}
}
//以34567(10)=2111(x)为例
//2*x^3=<34567<3*x^3
//34567/3 <x^3<= 34567/2
//pow(34567/3,1/3)<x<=pow(34567/2,1/3) //开3次方
long long lo, hi, mid;
double temp = to_num(b[0]); double exp = len - 1;
lo = pow(t1 / (temp + 1), 1 / exp);
hi = pow(t1 / temp, 1 / exp);
//则 x属于(lo,hi],左开右闭
//pat.3特殊案例 1(2)=97(x)
//lo = 0, hi=0,mid=0会一直卡在循环里
//可以在下面的while{}主体中
//加入mid==0的判断然后break,能过pat.3
//但由于pat.19的case，在这里判断lo==hi更好
//(lo,hi]在lo==hi时，理论上确定了不可能存在x
if (lo == hi) { cout << "Impossible"; return 0; }
//二分查找
while (lo <= hi) { //一定要写等于号！不然当ans=hi时，mid永远取不到hi
mid = (lo + hi) / 2;
//if (mid == 0) break;
t2 = 0;
for (int i = 0; i < len; ++i) {
t2 = t2 * mid + to_num(b[i]);
if (t2 > t1) {//说明当前的mid作为基数太大了
hi = mid - 1;
break;
}
}//end-for-计算t2
if (t2 == t1) {
cout << mid;
return 0;
}
if (t2 < t1) {//当前mid太小
lo = mid + 1;
}
}
//二分查找失败
cout << "Impossible";
return 0;
}
#include<string>
#include<cmath>
using namespace std;
//1010 Radix
//给出2个整数，和其中一个的进制，求另一个进制radix使两数相等
//如6(10)=110(2)，已知6 110 1 10，
//代表第一个数字6的进制为10，求110的进制使6(10)=110(radix)
//由题目可知数字部分不超过36
int num[36];
int to_num(char c) {
if (c >= 'a' && c <= 'z') {
return num[c - 'a' + 10];
}
else if (c >= '0' && c <= '9') {
return num[c - '0'];
}
else {
return -1;
}
}
int main() {
string a, b;
int tag, r;
unsigned long long t1 = 0, t2 = 0;
cin >> a >> b >> tag >> r;
if (a == b) { cout << r; return 0; } //pat.10
//初始化
for (int i = 0; i<36; ++i) num[i] = i;
//保证r指向a的进制，求b的进制
if (tag == 2) {
a.swap(b);
}
int len = a.size();
t1 = 0;
for (int i = 0; i < len; ++i) {
//t1 += to_num(a[i])*pow((double)r, double(len - i - 1));
//从别人那里学到一个不用pow()的计算方法
t1 = t1 * r + to_num(a[i]); //神奇又简便！
}
len = b.size();
if (len == 1) { //pat.1 长度为1的时候不能用下面的pow计算lo和hi
if (to_num(b[0]) == t1) {
cout << t1 + 1;
return 0;
}
else {
cout << "Impossible";
return 0;
}
}
//以34567(10)=2111(x)为例
//2*x^3=<34567<3*x^3
//34567/3 <x^3<= 34567/2
//pow(34567/3,1/3)<x<=pow(34567/2,1/3) //开3次方
long long lo, hi, mid;
double temp = to_num(b[0]); double exp = len - 1;
lo = pow(t1 / (temp + 1), 1 / exp);
hi = pow(t1 / temp, 1 / exp);
//则 x属于(lo,hi],左开右闭
//pat.3特殊案例 1(2)=97(x)
//lo = 0, hi=0,mid=0会一直卡在循环里
//可以在下面的while{}主体中
//加入mid==0的判断然后break,能过pat.3
//但由于pat.19的case，在这里判断lo==hi更好
//(lo,hi]在lo==hi时，理论上确定了不可能存在x
if (lo == hi) { cout << "Impossible"; return 0; }
//二分查找
while (lo <= hi) { //一定要写等于号！不然当ans=hi时，mid永远取不到hi
mid = (lo + hi) / 2;
//if (mid == 0) break;
t2 = 0;
for (int i = 0; i < len; ++i) {
t2 = t2 * mid + to_num(b[i]);
if (t2 > t1) {//说明当前的mid作为基数太大了
hi = mid - 1;
break;
}
}//end-for-计算t2
if (t2 == t1) {
cout << mid;
return 0;
}
if (t2 < t1) {//当前mid太小
lo = mid + 1;
}
}
//二分查找失败
cout << "Impossible";
return 0;
}
发表于 2019-01-13 18:37:54
回复(0)
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
char n1[15],n2[15];
int mark[256],radix,tag;
void init(){
char c;
for(c='0';c<='9';c++)mark[c]=c-'0';
for(c='a';c<='z';c++)mark[c]=c-'a'+10;
}
LL compute(char x[],int r){
int len;
LL ans=0;
len=strlen(x);
for(int i=0;i<len;i++)ans=ans*r+mark[x[i]];
return ans;
}
int cmp(char x[],LL r,LL t){//注意溢出超过long long的情况
LL num=compute(x,r);
if(num<0)return 1;
if(num<t)return -1;
else if(num==t)return 0;
else return 1;
}
int binsrch(LL t,char y[],LL low,LL high){
LL mid;
while(low<=high){
mid=(low+high)/2;
int m=cmp(y,mid,t);
if(m<0)low=mid+1;
else if(m>0)high=mid-1;
else return mid;
}
return -1;
}
int main(){
//freopen("A1010.txt","r",stdin);
init();
char temp[15];
LL low=0,high,t;
int ans;
scanf("%s %s %d%d",n1,n2,&tag,&radix);
if(tag==2){
strcpy(temp,n1);
strcpy(n1,n2);
strcpy(n2,temp);
}
t=compute(n1,radix);
for(int i=0;i<strlen(n2);i++)if(mark[n2[i]]>low)low=mark[n2[i]];
low++;
high=max(low,t)+1;
ans=binsrch(t,n2,low,high);
if(ans==-1)printf("Impossible");
else printf("%lld",ans);
return 0;
}
发表于 2017-08-21 20:53:19
回复(0)
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char str1[12],str2[12];
long long n,m=1;
int get_min_rad(int len,char *str){
int num,min_rad=1;
for(int i=0;i<len;i++){
num=str[i]<'a'?str[i]-'0':str[i]-'a'+10;
min_rad=max(num+1,min_rad);
}
return min_rad;
}
long long get_N1(int len,char *str,long long radix){
//printf("radix=%lld\n",radix);
long long num=0;
int t;
num=str[0]<'a'?str[0]-'0':str[0]-'a'+10;
for(int i=1;i<len;i++){
t=str[i]<'a'?str[i]-'0':str[i]-'a'+10;
if(num>(m-t)/radix)//防止溢出
return n+1;
num=num*radix+t;
}
return num;
}
long long search(int len,char *str,long long left,long long right){
long long mid,num=0;
//printf("%n==lld\n",n);
while(left<=right){
mid=left+(right-left)/2;
num=get_N1(len,str,mid);
//printf("%num==lld\n",num);
if(num==n){
return mid;
}
else if(num>n){
right=mid-1;
}
else{
left=mid+1;
}
}
return -1;
}
long long solve(int len,char *str){
int min_rad=get_min_rad(len,str);
long long ans=search(len,str,min_rad,n+1);
if(ans>0&&len==1)
ans=min_rad;
return ans;
}
int main(){
//freopen("in.txt","r",stdin);
int tag,radix;
scanf("%s%s%d%d",str1,str2,&tag,&radix);
int len1,len2,min_rad=1;
long long ans;
len1=strlen(str1);
len2=strlen(str2);
m=(m<<63)-1;
if(tag==1){
min_rad=get_min_rad(len1,str1);
if(radix<min_rad){
ans=-1;
}
else{
n=get_N1(len1,str1,radix);
m=n;
ans=solve(len2,str2);
}
}
else{
min_rad=get_min_rad(len2,str2);
if(radix<min_rad){
ans=-1;
}
else{
n=get_N1(len2,str2,radix);
m=n;
ans=solve(len1,str1);
}
}
if(ans>0){
printf("%lld\n",ans);//ans也可能是long long
}
else{
printf("Impossible\n");
}
return 0;
}
之前一直段错误，也不知道改哪了就不报了，牛客的数据比pat严格不少。在pat上radix用int都能过。
这个题关键是二分，还要注意溢出。
发表于 2016-07-23 11:04:26
回复(1)
注意进制可能会很大，用二分法降低时间复杂度
def getNum(radix, NList): l = len(NList); num = 0 for i in range(l): num += NList[i]*(radix**(l-i-1)) return num def str2numList(n): NList = [] for i in n: if i>='0' and i<='9': NList.append(int(i)) else: NList.append(ord(i)-87) return NList N1, N2, tag, radix = raw_input().split() radix = int(radix) if tag == '1': num = getNum(radix, str2numList(N1)) target = str2numList(N2) else: num = getNum(radix, str2numList(N2)) target = str2numList(N1) left = max(target)+1; right = max(num, left) isFind = False; rlt = 0 while left <= right: mid = (left + right)/2 tempRlt = getNum(mid, target) if num == tempRlt: rlt = mid; isFind = True right = mid - 1 elif num < tempRlt: right = mid - 1 else: left = mid + 1 if isFind: print rlt else: print 'Impossible'
发表于 2016-02-29 14:51:18
回复(0)
问题信息
难度：
16条回答
15收藏
8858浏览
通过挑战的用户
-
2023-03-14 11:52:49
-
2023-03-08 22:01:44 -
2023-03-06 12:11:45 -
2023-03-03 20:51:32
-
2023-02-23 21:45:15
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
