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

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数字的最小区间。

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

#include <cstdio>

#include <iostream>

#include <cmath>

#include <algorithm>

#include <string>

#include <cstring>

#include <vector>

#include <queue>

// #define _ ios::sync_with_stdio(false)

// #define cin.tie(0)

using namespace std;

// #define rep(i,x,y) for(int i=x;i<y;i++)

typedef long long ll;

const int MAXN=2e5+5;

vector<ll> v;

int main()

{

    ll x,y,l,r;

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

    ll tx,ty;

    ll d1=r;

    for(int i=0;i<=61;i++)

    {

        if(i!=0)

            d1/=x;

        if(d1==0)

            break;

        if(i==0)

            tx=1;

        else

        tx*=x;

        ll d2=r;

        for(int j=0;j<=61;j++)

        {

            if(j!=0)

                d2/=y;

            if(d2==0)

                break;

            if(j==0)

                ty=1;

            else

                ty*=y;

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

                v.push_back(tx+ty);

        }

    }

    if(!v.size())

    {

        cout<<r-l+1<<endl;

        return 0;

    }

    ll ans=0;

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

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

    {

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

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

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

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

        else

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

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

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

The Golden Age

最新文章

热门文章