题解 【CF813B The Golden Age】

Solution

题目大意不需要说了。这里我们考虑枚举 $a,b$，构造出不是幸运数字的满足题目所给区间的数字，存在一个 vector 里，然后将 vector 中的数字排序，依次做差得出幸运数字的最大连续长度就可以了，注意：这里得出长度应该是两个数字之差再减一，才可以得出它们中间数字的长度。

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define gc getchar
inline ll read() {
    ll c = gc(), t = 1, n = 0;
    while(isspace(c)) { c = gc(); }
    if(c == '-') { t = -1, c = gc(); }
    while(isdigit(c)) { n = n * 10 + c - '0', c = gc(); }
    return n * t;
}
#undef gc

ll x,y,l,r;
vector <ll> p; 

int main() {
    x = read(); y = read(); l = read(); r = read();
    for(ll i = 1;;i *= x) { //构造形如 x^a + y^b 的形式
        for(ll j = 1;;j *= y) {
            if(i + j >= l && i + j <= r) p.push_back(i + j);    //如果满足区间就放到 vector 里面去
            if(r / j < y) break;    //作商之后如果小于 y，就证明乘 y 之后的所有数字都不能满足，跳出循环
        }
        if(r / i < x) break;    //同理
    }
    sort(p.begin(),p.end());
    if(p.size() == 0) printf("%lld\n",r - l + 1);
    else {
        ll ans = max(p[0] - l,r - p[p.size() - 1]); //边界值不要忘记特判
        for(int i = 1;i < p.size();i++) ans = max(ans,p[i] - p[i - 1] - 1);
        printf("%lld\n",ans);
    }
    return 0;
}