Educational Codeforces Round 22 B. The Golden Age

#include <iostream> 
#include <stdio.h> 
#include <string.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <vector> 
#include <math.h> 
#include <bitset> 
#include <algorithm> 

using namespace std;

#define X first
#define Y second
#define eps 1e-2
#define gcd __gcd
#define pb push_back
#define PI acos(-1.0)
#define lowbit(x) (x)&(-x)
#define bug printf("!!!!!\n");
#define mem(x,y) memset(x,y,sizeof(x))

typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef unsigned long long uLL;
#define int long long 
const int N = 1e5+2;
const int INF  = 1<<30;
const int mod  = 1e9+7;

int x,y,L,R;
std::vector<int> v;
map<int,int> mp;
void solve(){
    
    scanf("%lld%lld%lld%lld",&x,&y,&L,&R);
    for(int i=1;i<=R;i=i*x){
    
        for(int j=1;j+i<=R;j=j*y){
    
            if(i+j>=L&&i+j<=R&&mp.count(i+j)==0){
    
                v.push_back(i+j);
                mp[i+j]=1;
            }
            // cout<<i<<" "<<j<<" "<<(R-i)/j<<" "<<y<<endl;
            if((R-i)/j<y) break;
        }
        if(R/i<x) break;
    }
    v.push_back(R+1);
    sort(v.begin(),v.end());
    int st=L-1,ans=0;
    for(int i=0;i<v.size();i++){
    
        if(ans<v[i]-st-1){
    
            ans=v[i]-st-1;
        }
        st=v[i];
    }
    cout<<ans<<endl;
    
    return;
}

int32_t main()
{
    
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// ios::sync_with_stdio(false);
    int t = 1;
    //scanf("%d",&t);
    while(t--){
    
    // printf("Case %d: ",cas++);
        solve();
    }
    return 0;
}