第三章进位制 AcWing 1482. 进制

妖狐艹你老母 2024-04-07 12:36 21阅读 0赞

## 第三章 进位制 AcWing 1482. 进制 ##

### 原题链接 ###

[AcWing 1482. 进制][AcWing 1482.]

### 算法标签 ###

数学 进位制 二分 秦九韶算法

### 我的代码 ###

### 思路 ###

对符合要求的进制数（符合要求的最小进制-36）依次枚举  
22/24

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    using namespace std;
    typedef pair<int, int> PII;
    const int N=25;
    //int t, n, m, cnt, ans; 
    inline int rd(){
      int s=0,w=1;
      char ch=getchar();
      while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
      while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
      return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    int f(string a, int b){
        int sum=0;
        for(auto m:a){
            if(m>='0'&&m<='9'){
            	sum+=((m-'0')*pow(b, cnt));
    		}else{
    			sum+=((m-'a'+10)*pow(b, cnt));
    		}
        }
        return sum;
    }
    int Max(string a){
        int mx=0;
        rep(i, 0, a.size()){
            char m=a[i];
            if(m>='0'&&m<='9'){
            	mx=max(mx, (m-'0')*1ll);
    		}else{
    			mx=max(mx, (m-'a'+10)*1ll);
    		} 
        }
        return mx+1;
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	string a, b;
    	int c, d, e;
    	cin>>a>>b>>c>>d;
    	bool flag=false;
    	if(c==1){
    	    e=f(a, d);
    	    int t=Max(b);
    	    rep(i, t, 37){
    	        if(f(b, i)==e){
    	       		flag=true;
    	       		printf("%lld\n", i);
    	       		break;
    	    	}
    		}
    		if(!flag){
    	   		printf("Impossible\n");
    		}
    	}else{
    	    e=f(b, d);
    	    int t=Max(a);
    	    rep(i, t, 37){
    	   		if(f(a, i)==e){
    	       		flag=true;
    	       		printf("%lld\n", i);
    	       		break;
    	    	}
    		}
    		if(!flag){
    	   		printf("Impossible\n");
    		}
    	}
    	return 0;
    }

### 正确思路 ###

对符合要求的进制数（符合要求的最小进制- 3 ∗ 1 0 15 3\*10^\{15\} 3∗1015）二分枚举  
![在这里插入图片描述][03b6446a49d549f3b2cc0704ea523c32.png]

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<bits/stdc++.h>
    #define int long long
    #define x first
    #define y second
    #define ump unordered_map
    #define pq priority_queue
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    using namespace std;
    typedef pair<int, int> PII;
    const int N=25;
    //int t, n, m, cnt, ans; 
    inline int rd(){
      int s=0,w=1;
      char ch=getchar();
      while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
      while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
      return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    int get(char c){
        if(c<='9'){
            return c-'0';
        }
        return c-'a'+10;
    } 
    int f(string a, int b){
        int res=0;
        for(auto c:a){
        	// 超过给定题意范围 返回较大值 表示未找到
            if((double)res*b+get(c)>1e16){
                return 1e18;
            }
            // 秦九韶算法核心
            res=res*b+get(c);
        }
        return res;
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	string a, b;
    	int c, d, e;
    	cin>>a>>b>>c>>d;
    	if(c==2){
    		// 交换顺序 避免代码冗余
    	    swap(a, b);  
    	} 
        e=f(a, d);
        int l=0, r=max(e, 36ll);
        for(auto c:b){
            l=max(l, get(c)+1);    
        } 
        while(l<r){
            int mid=l+r>>1;
            if (f(b, mid)>=e){
                r=mid;    
            } 
            else{
                l=mid+1;    
            }
        }
        if(f(b, r)!=e){
            puts("Impossible");    
        }
        else{ 
            cout<<r<<endl;
        }
    	return 0;
    }

参考文献  
[AcWing 1482. 进制（PAT甲级辅导课）y总视频讲解][AcWing 1482.]  
[AcWing 1482. 进制（PAT甲级辅导课）题解][AcWing 1482. _PAT]

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 1482.]: https://www.acwing.com/video/1012/
[03b6446a49d549f3b2cc0704ea523c32.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4ef84d230fd3488ba25b070598c797e6.png
[AcWing 1482. _PAT]: https://www.acwing.com/solution/content/11408/
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8dc0e384ca7e46f5aaefbad25ac67349.png