即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

Codeforces 813B The Golden Age 题解

编程语言 m0_37729344 17℃ 0评论
本文目录
[隐藏]

1.题意

1.1.如果一个数可以表示为给定的两个数的非负整数幂之和,那么它就是不幸的,给定两个数a,b,求l到r区间内最多有多少个连续数字是非不幸的

2.思路

2.1.将a和b不超过r的非负整数幂先算出来,然后枚举相加,去重,将[l,r]之间的和放进vector,判断相邻两数之差,取最大,注意考虑首尾和vector为空的情况

3.代码

#include 
#include 
#include 
#include 
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;i1;
    cnt=0;
    rr=r;
    while(rr>0)
    {
        rr/=y;
        cnt++;
    }
    for(long long i=0;ifor(long long i=0;ifor(long long j=0;jif(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;iif(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;
}

转载请注明:CodingBlog » Codeforces 813B The Golden Age 题解

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情