Codeforces 813B The Golden Age(数学+枚举)

题目大意：如果一个数t=x^a+y^b(a,b都是大于等于0的整数)那就是一个unlucky数字。给你x,y,l,r(2 ≤ x, y ≤ 10^18, 1 ≤ l ≤ r ≤ 10^18),求出l到r内没有unlucky数字的最小区间。

解题思路：可以知道a，b最多也不会超过60（2^60>1e18），所以可以直接枚举x^a+y^b的值存到vector里，然后排序，遍历一下vector,找出v[i+1]-v[i]-1(因为两端都是unlucky数字所以要两个端点都不算在长度内)最大的区间即可。要注意vector为空和两个端点的特判。还有数字的溢出问题，这个没办法直接判断是否溢出，可以通过使用一个d=r，比如每次x次方加一的时候，就将d/x，当d==0说明x^a已经超出r的范围了。

代码：

 #include<iostream>

 #include<vector>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 vector<ll>v;

 int main(){

     ll x,y,l,r;

     cin>>x>>y>>l>>r;

     ll tx,ty;

     ll d1=r;

     for(int i=;i<=;i++){

         if(i!=)

             d1/=x;

         if(d1==)

             break;

         if(i==)

             tx=;

         else

             tx*=x;

         ll d2=r;

         for(int j=;j<=;j++){

             if(j!=)

                 d2/=y;

             if(d2==)

                 break;

             if(j==)

                 ty=;

             else

                 ty*=y;

             if(tx+ty>=l&&tx+ty<=r){

                 v.push_back(tx+ty);

             }

         }

     }

     //vector为空的情况

     if(!v.size()){

         cout<<r-l+<<endl;

         return ;

     }

     ll ans=;

     sort(v.begin(),v.end());

     for(int i=;i<v.size();i++){

         //如果l不是unlucky数字，那就额外计算v[0]-l这段区间

         if(i==&&v[]!=l)

             ans=max(ans,v[i]-l);

         //如果r不是unlucky数字，就额外计算r-v[v.size()-1]这段区间

         if(i==v.size()-){

             if(!sign2)

                 ans=max(ans,r-v[i]);

         }

         else

             ans=max(ans,v[i+]-v[i]-);

     }

     cout<<ans<<endl;

 }

巴特西

Codeforces 813B The Golden Age(数学+枚举)

最新文章

热门文章