题解 【CF813B The Golden Age】

TRZ_2007

2021-03-20 20:00:28

Solution

**[题解 【CF813B The Golden Age】](https://www.luogu.com.cn/problem/CF813B)** # Solution 题目大意不需要说了。这里我们考虑枚举 $a,b$,构造出**不是**幸运数字的**满足题目所给区间**的数字,存在一个 ```vector``` 里,然后将 ```vector``` 中的数字排序,依次做差得出幸运数字的最大连续长度就可以了,**注意:这里得出长度应该是两个数字之差再减一,才可以得出它们中间数字的长度**。 # Code ```cpp #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; } ```