出题人题解 | #进制的交集#

原题解链接：https://ac.nowcoder.com/discuss/150263

解法很多，比如DP,贪心，二分。

题解里提供二分的解法。

时间复杂度$O(T\ast log(1e18)\ast 2)O(T*log(1e18)*2)$

我们发现，最后交出来的答案的区间在小进制下一定连续的。

所以我们考虑，所以我们二分出答案区间在小进制下的左右端点，然后做差就是答案。

注意，特判两段区间没交集的时候请输出0而不是负数或者其他的结果。

#include<bits/stdc++.h>
using namespace std;
long long change_m_10(const char *s,int m)//把m进制的s转换成10进制数并返回
{
    if(s[0]=='+')
    {
        return change_m_10(s+1,m);
    }
    if(s[0]=='-')
    {
        return change_m_10(s+1,m)*-1;
    }
    long long sum=0;
    int l=strlen(s);
	for(int i=0;i<l;i++)
	{
		if(s[i]>='A'&&s[i]<='Z')
		{
			sum=sum*m+s[i]-'A'+10;
		}
		else
		{
			sum=sum*m+s[i]-'0';
		}
	}
	return sum;
}
void change_10_m(long long x,int m,char s[])//把10进制的x转换成m进制并存入s数组
{
    const char f[20]="0123456789ABCDEF";
    int stk[105],top=0;
    bool sign;
    sign=x<0;
    if(sign)x*=-1;
    if(!x)
    {
        s[0]='0';
        s[1]='\0';
        return;
    }
    while(x)
	{
		int a=x%m;
        x=x/m;
        if(a<0)
		{
        	x++;
            a=a-m;
        }
        stk[++top]=a;
    }
    int l=0;
    if(sign)
    {
        s[l++]='-';
    }
	while(top)
	{
		s[l++]=f[stk[top--]];
    }
    s[l]='\0';
    return;
}
long long change(const char *s)
{
    long long ans=0;
    int l=strlen(s);
	for(int i=0;i<l;i++)
    {
        ans=ans*10+s[i]-'0';
    }
    return ans;
}
int T,J1,J2;
string l1,r1,l2,r2;
char save[105];
long long L,R;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&J1,&J2);
        cin>>l1>>r1>>l2>>r2;
        if(J1>J2)
        {
            swap(J1,J2);
            swap(l1,l2);
            swap(r1,r2);
        }
        string temp;
        temp.clear();
        for(int i=1;i<=18;++i)
        {
            temp+='0'+J1-1;
        }
        L=0;
        R=change_m_10(temp.c_str(),J1);
        long long x=change(l2.c_str());
        long long ansx;
        while(L<=R)
        {
            long long mid=(L+R)/2;
            change_10_m(mid,J1,save);
            if(change(save)>=x)
            {
                ansx=mid;
                R=mid-1;
            }
            else
            {
                L=mid+1;
            }
        }
        L=0;
        R=change_m_10(temp.c_str(),J1);
        long long y=change(r2.c_str());
        long long ansy;
        while(L<=R)
        {
            long long mid=(L+R)/2;
            change_10_m(mid,J1,save);
            if(change(save)<=y)
            {
                ansy=mid;
                L=mid+1;
            }
            else
            {
                R=mid-1;
            }
        }
        long long ansl=change_m_10(l1.c_str(),J1);
        long long ansr=change_m_10(r1.c_str(),J1);
        ansl=max(ansl,ansx);
        ansr=min(ansr,ansy);
        printf("%lld\n",max(ansr-ansl+1,0LL));
    }
    return 0;
}