PAT1010 Radix（进制转换）

分析：给定一对正整数，例如6和110，这个等式6 = 110是否为真？答案是“是”，如果6是十进制数，110是二进制数的话。现在对于任意一对正整数N1和N2，你的任务是找到一个数字的进制，而另一个数字的进制是给定的。

分析：修改了一下，现在是24/25。
（1）首先确定让你判断的数的进制，它的下限应该是自身每一位最大值再加1，比如2d34，那么进制的下限就应该是d+1也就是14.这个数进制的上限就是另外一个数的大小。
（2）然后二分这个区间$[minRadix,maxRadix]$，判断这两个数是否相等。
（3）注意：范围可能非常的大，开unsigned long long

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
string s1,s2;
ull n1,n2,tag,radix;
ull tran(string s,ull q){
    ull len=s.length();ull tmp=0;for(ull i=0;i<len;i++){
    if(s[i]>='0'&&s[i]<='9') {
    tmp=tmp*q+s[i]-'0';}else if(s[i]>='a'&&s[i]<='z') {
    tmp=tmp*q+s[i]-'a'+10;}}return tmp;
}void solve(string s,ull num){
    ull len=s.length();ull lowRadix=1;ull maxRadix=num;bool flag=false;for(ull i=0;i<len;i++){
    ull x=-1;if(s[i]>='0'&&s[i]<='9'){
    x=s[i]-'0';}else if(s[i]>='a'&&s[i]<='z') {
    x=s[i]-'a'+10;}lowRadix=max(x,lowRadix);}lowRadix++;                 //得到这个数的进制下限maxRadix=num;                //得到这个数的上限，就是另外的那个数ull l=lowRadix;ull r=maxRadix;ull mid=-1;while(l<=r){
    mid=(l+r)/2;if(tran(s,mid)<num){
    l=mid+1;}else if(tran(s,mid)>num) {
    r=mid-1;}else {
    flag=true;break;}}if(!flag) cout<<"Impossible"<<endl;else{
    cout<<mid<<endl;}
}
int main(){
    std::ios::sync_with_stdio(false);cin>>s1>>s2;cin>>tag>>radix;if(tag==1){
    n1=tran(s1,radix);solve(s2,n1);}else{
    n2=tran(s2,radix);solve(s1,n2);}return 0;
}

得分10/25，明天补。

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int n1,n2,tag,radix;
int tran(string s,int q){
    int len=s.length();int tmp=0;for(int i=0;i<len;i++){
    if(s[i]>='0'&&s[i]<='9') {
    tmp=tmp*q+s[i]-'0';}else if(s[i]>='a'&&s[i]<='z') {
    tmp=tmp*q+s[i]-'a'+10;}}return tmp;
}void solve(string s,int num){
    int len=s.length();int ans=0;bool flag=false;int cur=0;char ch;for(int i=0;i<=35;i++){
    ans=tran(s,i);if(ans==num){
    flag=true;cur=i;break;}}if(cur>10){
    ch=cur-11+'a';}if(!flag) cout<<"Impossible"<<endl;else{
    if(cur>10) cout<<ch<<endl;else cout<<cur<<endl;}
}
int main(){
    cin>>s1>>s2;cin>>tag>>radix;if(tag==1){
    n1=tran(s1,radix);solve(s2,n1);}else{
    n2=tran(s2,radix);solve(s1,n2);}return 0;
}