Educational Codeforces Round 22 B. The Golden Age（暴力）

时间：2021-05-24 13:35:45

题目链接：http://codeforces.com/contest/813/problem/B

题意：就是有一个数叫做不幸运数，满足题目的 n = x^a + y^b,现在给你一个区间[l,r]，让你找一个在这个区间里面一个最长的区间使得这个区间里面的所有数都不是不幸运数，让你输出最长区间的区间长度 。

先用两个数组将x的n次方和y的n次方存起来，然后暴力枚举，用map将符合的条件的数存起来，不幸运数的区间就是两个幸运数的位置之差相减再减1。（注意map迭代器的用法）

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define pi acos(-1)

const int INF = 0x3f3f3f3f;

const ll N=1e18;

map<ll,ll>ma;

ll x[],y[];

int  main()

{

    memset(x,,sizeof(x));

    memset(y,,sizeof(y));

    ll a,b,l,r;

    scanf("%I64d%I64d%I64d%I64d",&a,&b,&l,&r);

    x[]=;

    y[]=;

    ma[l-]=;

    ma[r+]=;

    for(int i=; x[i-]<=N/a; i++)

        x[i]=x[i-]*a;

    for(int i=; y[i-]<=N/b; i++)

        y[i]=y[i-]*b;

    for(int i=; x[i]!=; i++)

        for(int j=; y[j]!=; j++)

            if(x[i]+y[j]<=r&&x[i]+y[j]>=l)

                ma[x[i]+y[j]]=;

    map<ll,ll>::iterator fir,sec;

    sec=ma.begin();

    fir=ma.begin();

    sec++;

    ll ans=;

    for(; sec!=ma.end(); fir++,sec++)

        ans=max(ans,sec->first-fir->first-);

    printf("%I64d",ans);

    return ;

}

相关文章