即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

Educational Codeforces Round 22-B. The Golden Age-暴力枚举+map

编程语言 qq_35781950 13℃ 0评论

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
using namespace std;
/*这道题好暴力。
首先要知道longlong64位,所以65就能存下。
然后暴力用map来存一下位数。
66的。

*/
typedef long long int ll;
const ll N=1e18+1;
ll x[100],y[100];
maps;
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<
    //cout<
      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::iterator fir,sec;
       sec=s.begin();
       fir=s.begin();
       sec++;
       ll ans=0;
       //for(fir;fir!=s.end();fir++)
          //cout<first<
       for(;sec!=s.end();sec++,fir++)
       {   ans=max(ans,sec->first-fir->first-1);


       }
       cout<return 0;
}

转载请注明:CodingBlog » Educational Codeforces Round 22-B. The Golden Age-暴力枚举+map

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情