题解归档 - cf813B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf813B
• 本地来源：problems/cf813B/idea.md
• 题目链接：https://codeforces.com/contest/813/problem/B
• 原始标题：CF813B — The Golden Age

思路

CF813B — The Golden Age

题意

年份 n 为不幸年当且仅当存在非负整数 a,b 使 n = x^a + y^b。在 [l,r] 内求最长连续「幸运年」区间长度；若全不幸则输出 0。

做法

枚举 x^a、y^b（均 ≤ r，约 60 项），收集所有 x^a+y^b ∈ [l,r] 的不幸年，排序去重后在相邻不幸年之间（及区间两端）取最大空隙。

验证

官方 3 组样例通过；stress.py 分批对拍 100+ 组与 brute 一致。

代码

来源：problems/cf813B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 12:10:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll>bad;
ll x,y,l,r,i,j,k,ans,cnt,cur,pd;
int main(){
    cin>>x>>y>>l>>r;
    cur=1;
    while(cur<=r){
        pd=1;
        while(pd<=r){
            __int128 zc=(__int128)cur+pd;
            if(zc>=l and zc<=r) bad.push_back((ll)zc);
            if(pd>(__int128)r/y) break;
            pd*=y;
        }
        if(cur>(__int128)r/x) break;
        cur*=x;
    }
    sort(bad.begin(),bad.end());
    bad.erase(unique(bad.begin(),bad.end()),bad.end());
    ans=0;
    cur=l-1;
    for(i=0;i<(ll)bad.size();i++){
        ans=max(ans,bad[i]-cur-1);
        cur=bad[i];
    }
    ans=max(ans,r-cur);
    cout<<ans<<"\n";
    return 0;
}