题解：AT_abc293_f [ABC293F] Zero or One

shy_lihui · 2024-11-19 11:04:45 · 题解

思路分析

暴力会挂。

考虑两种情况 b \le 10^3 和 b > 10^3 ，再把这两种情况拼起来就好了。可能说的有点抽象。

不难发现：1001^6>10^{18} 。所以对于一个合法 b 进制肯定不超 6 位。所以有 2^{6}-1 种可能。可以枚举 b 的值。你会发现对于一个 b 进制下的数，那么 b 越大这个数十进制下就越小。符合单调性直接上二分！

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool check1(int a,int b)//判断数字 a 在 b  进制下是否只有 1,0 。 
{
    while(a>0)
    {
        if(a%b>1)
        {
            return 0;
        }
        a/=b;
    }
    return 1;
}
int cal(int b,int sum,int a)//进制转换 
{
    int res=0;
    int now=1;
    while(sum>0)
    {
        if(sum%2==1)
        {
            res+=now;
            if(res>a)
            {
                return a+1;
            }
        }
        sum/=2;
        if(now>a/b+1&&sum>0)
        {
            return a+1;
        }
        now*=b;
    }
    return res;
}
bool check2(int a,int sum)//二分查找 a 在几进制下是 sum （sum 为 1,0 构成）？
{
    int l=1001;
    int r=a;
    bool res=0;
    while(l<=r)
    {
        int mid=(l+r)/2;
        int now=cal(mid,sum,a);
        if(now==a)
        {
            return 1;
        }
        if(now<a)
        {
            l=mid+1;
        }
        if(now>a)
        {
            r=mid-1;
        }
    }
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t,a;
    cin>>t;
    while(t--)
    {
        cin>>a;
        int ans=1;//本轮答案。 
        for(int b=3;b<=min(1000LL,a);b++)// 3~1000 暴力枚举。 
        {
            ans+=check1(a,b);
        }
        if(a>1000)//超过一千。 
        {
            for(int sum=1;sum<=(1<<6)-1;sum++)//1~2^6-1 枚举。 
            {
                ans+=check2(a,sum);
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}