http://codeforces.com/contest/813/problem/B 给定一个a和b 如果满足 pow(a,i)+pow(b,j),就说这个数不幸运 求一个区间内最大的没有不幸运数的区间。 数据范围 Input The first line contains four integer numbers x, y, l and r (2 ≤ x, y ≤ 1018, 1 ≤ l ≤ r ≤ 1018). 方法：暴力枚举， 用map存数，方便计算区间。 map count用来判断是否有没有这个数 用find来判断这个数的位置
#include<bits/stdc++.h> using namespace std; /*这道题好暴力。 首先要知道longlong64位，所以65就能存下。 然后暴力用map来存一下位数。 66的。 */ typedef long long int ll; const ll N=1e18+1; ll x[100],y[100]; map<ll,ll>s; int main() {//freopen("t.txt","r",stdin); ll a,b,l,r; cin>>a>>b>>l>>r; memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); x[0]=1; y[0]=1; //cout<<l<<endl; //cout<<r<<endl; s[l-1]=1; s[r+1]=1; //x[1]=a; //y[1]=b; for(int i=1;x[i-1]<=N/a;i++) x[i]=x[i-1]*a; for(int j=1;y[j-1]<=N/b;j++) y[j]=y[j-1]*b; for(int i=0;x[i]!=0;i++) for(int j=0;y[j]!=0;j++) if(x[i]+y[j]<=r&&s.count(x[i]+y[j])==0&&x[i]+y[j]>=l) s[x[i]+y[j]]=1; map<ll,ll>::iterator fir,sec; sec=s.begin(); fir=s.begin(); sec++; ll ans=0; //for(fir;fir!=s.end();fir++) //cout<<fir->first<<endl; for(;sec!=s.end();sec++,fir++) { ans=max(ans,sec->first-fir->first-1); } cout<<ans<<endl; return 0; }