区间-CodeForces 813B-The Golden Age

红太狼 2022-05-16 11:04 179阅读 0赞

*  # 区间-CodeForces 813B-The Golden Age #

--------------------

*  ## 题目链接：[B. The Golden Age][] ##
 *  ## 思路： ##

如果*n* = *x^**a* + *y^b( b>=0,a>=0），则n称为*Unlucky year，如果一个年份区间中没有Unlucky year，叫做Golden Age，给定一个区间l~r，求出最大的Golden Age长度

**穷举出区间范围内全部的Unlucky year，计算相邻Unlucky year的间距，取最大值**

***一个很坑的地方，数据很大，很容易爆精度，所以在穷举x，y的指数值时降幂检测前一个的值***

*  ## 代码： ##

#include<iostream>
    #include<algorithm>
    using namespace std;
    #define MAX_SIZE 10200
    
    long long Left[MAX_SIZE],Right[MAX_SIZE],Unlucky_year[MAX_SIZE];
    
    int main()
    {
        long long x,y,l,r;
        cin>>x>>y>>l>>r;
        Left[0]=1;
        Right[0]=1;
        int cnt1=1,cnt2=1,cnt3=0;
        long long Max_Inter=0;
        while(r/x>=Left[cnt1-1])   //while的条件很重要，不然会爆精度
        {
            Left[cnt1]=Left[cnt1-1]*x;
            cnt1++;
        }
        while(r/y>=Right[cnt2-1])
        {
            Right[cnt2]=Right[cnt2-1]*y;
            cnt2++;
        }
        for(long long i=0;i<cnt1;i++)
        {
            for(long long j=0;j<cnt2;j++)
            {
                //cout<<Left[i]+Right[j]<<endl;
                if(Left[i]+Right[j]>=l&&Left[i]+Right[j]<=r)
                    Unlucky_year[cnt3++]=Left[i]+Right[j];  //记录unluckyear
            }
        }
        sort(Unlucky_year,Unlucky_year+cnt3);  //排序
        if(cnt3==0)     //区间中没有unluckyear，那么给定的区间是最大长度
        {
            cout<<r-l+1<<endl;
            return 0;
        }
        Max_Inter=max(Unlucky_year[0]-l,r-Unlucky_year[cnt3-1]);//检测端点，可能在端点取最大值
        for(int i=1;i<cnt3;i++)   //
            Max_Inter=max(Max_Inter,Unlucky_year[i]-Unlucky_year[i-1]-1);  //相邻检测
        cout<<Max_Inter<<endl;
        return 0;
    }

[B. The Golden Age]: http://codeforces.com/problemset/problem/813/B