题意
如果一个数可以表示为给定的两个数的非负整数幂之和，那么它就是不幸的，给定两个数a,b，求l到r区间内最多有多少个连续数字是非不幸的
思路
将a和b不超过r的非负整数幂先算出来，然后枚举相加，去重，将[l,r]之间的和放进vector，判断相邻两数之差，取最大，注意考虑首尾和vector为空的情况
代码
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
vector<long long> xx,yy;
set<long long> s;
vector<long long> ss;
int main()
{
long long x,y,l,r,t,cnt,rr,ans;
scanf(
"%I64d%I64d%I64d%I64d",&x,&y,&l,&r);
t=
1;
cnt=
0;
rr=r;
while(rr>
0)
{
rr/=x;
cnt++;
}
for(
long long i=
0;i<cnt;i++)
{
xx.push_back(t);
t*=x;
}
t=
1;
cnt=
0;
rr=r;
while(rr>
0)
{
rr/=y;
cnt++;
}
for(
long long i=
0;i<cnt;i++)
{
yy.push_back(t);
t*=y;
}
for(
long long i=
0;i<xx.size();i++)
for(
long long j=
0;j<yy.size();j++)
{
if(s.find(xx[i]+yy[j])==s.end()&&xx[i]+yy[j]>=l&&xx[i]+yy[j]<=r)
{
s.insert(xx[i]+yy[j]);
ss.push_back(xx[i]+yy[j]);
}
}
sort(ss.begin(),ss.end());
ans=
0;
for(
long long i=
0;i<ss.size();i++)
{
if(i==
0)
ans=max(ans,ss[i]-l);
else ans=max(ans,ss[i]-ss[i-
1]-
1);
if(i==ss.size()-
1)
ans=max(ans,r-ss[i]);
}
if(ss.empty())
ans=max(ans,r-l+
1);
printf(
"%I64d\n",ans);
return 0;
}
