在此 Atcoder 问题中获取溢出和 TLE 问题

Question

我正在解决这个问题：D-Base n (https://atcoder.jp/contests/abc192/tasks/abc192_d)

它指出：

给定一个字符串 X 由 0 到 9 和一个整数组成米 . 让 d 是最大的数字 X . 有多少个不同的整数不大于米可以通过选择一个整数来获得 n 不小于 d + 1个看到 X 作为基地- n 数?

我反复解决了这个问题（这为我提供了小输入的正确答案）但它给了我 TLE 和溢出问题（请参阅我在 https://atcoder.jp/contests/abc192/submissions/20651499 提交的内容）。社论说一定要用Binary Search，我实现如下。但我仍然没有得到正确的输出。欢迎任何建议。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int M;
bool getInBase(unsigned long long int x, int base){
    int i=0;
    unsigned long long int ans = 0;
    while(x>0){
        int temp = x%10;
        ans += pow(base,i)*temp;
        i++;
        x/=10;
        if(ans>M) return false;
    }
    return (ans<M);
}

int main(){
    string X;
    cin>>X;
    cin>>M;
    int mx = 0;
    unsigned long long orig =0;
    for(char x: X){
        int sum = (int) x - (int)'0';
        if(sum>mx) mx = sum;
        orig = orig*10 + ((int)x - (int) '0');
    }
    int ans=0;
    unsigned long long int l = mx+1, r =M+1;
    unsigned long long int mid;
    while(l<r){
        mid = (l+r)/2;
        if(getInBase(orig,mid)){
            l = mid +1;
        }
        else{
            r = mid-1;
        }
    }
    
    cout<<l-mx;

}

Answer 1

ll convert(string x, ll base, ll m){
    ll ans=0;
    ll p=0;
    ll cur=1;
    for(int i=x.size()-1;i>=0;i--){
        if(cur<0 || ans<0)
            return m+1;
        ans+=(ll)(x[i]-'0')*cur;
        cur*=base;
        if(ans>m)
            return m+1;
    }
    return ans;
}
void solve(){
    ll i, j, m;
    string x;
    cin>>x>>m;
    int n=x.size();
    ll mx=0;
    for(auto i:x){
        mx=max(mx, (ll)(i-'0'));
    }
    if(n==1){
        cout<<(((ll)stoi(x))<=m)<<endl;
        return;
    }
    ll k=(ll)ceil(pow(m*1.0, 1.0/(n-1)));
    ll l=mx+1;
    ll r=k+1;
    ll ans=0;
    while(l<=r){
        ll mid=l+(r-l)/2;
        ll c=convert(x, mid, m);
        //cout<<"l = "<<l<<" mid ="<<mid<<" r= "<<r<<" c= "<<c<<endl;
        if(c<=m){
            ans=max(ans, mid);
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    cout<<max(0LL, ans-mx)<<endl;
}

在此 Atcoder 问题中获取溢出和 TLE 问题

Getting Overflow and TLE issues in this Atcoder question

c++

algorithm

binary-search

data-structures