http://codeforces.com/contest/813/problem/B
【题意】
满足n=x^a+y^b的数字为不幸运数字,a,b都是非负整数;
求闭区间[l,r]上的最长的连续幸运数字的区间长度。
2 ≤ x, y ≤ 10^18, 1 ≤ l ≤ r ≤ 10^18
【思路】
因为x,y>=2,所以x^a<=10^18,a不超过60
那么我们可以枚举所有的x^i
【注意】
这道题对于数字的处理一定要特别小心。
1.
while (num <= 1e18)
num = num * x
错误一
while (num * x <= 1e18)
num = num * x
错误二
这两种写法都不对,都会爆ll,因为num*x已经爆了ll,变成了<1e18的数
正确写法是:
while(num<=1e18/x)
{
num*=x;
}
写法一
int p=floor(log(r)/log(x));
int q=floor(log(r)/log(y));
写法二
写法二是用log求出个数后再for循环
2. pow函数精度不够,会WA
一开始我用了pow函数,结果WA了8发…..都是这个原因,后来手写了快速幂……以后不用这个函数了
ll fpow(ll x,int k)
{
long long res=;
while(k)
{
if(k&)res=res*x;
x=x*x;
k>>=;
}
return res;
}
fastpower
【Accepted】
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <ctime>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=;
ll a[maxn];
ll b[maxn];
ll x,y,l,r;
ll sum[maxn*maxn];
ll fpow(ll x,int k)
{
long long res=;
while(k)
{
if(k&)res=res*x;
x=x*x;
k>>=;
}
return res;
}
int main()
{
cin>>x>>y>>l>>r;
int p=floor(log(r)/log(x));
int q=floor(log(r)/log(y));
for(int i=;i<=p;i++)
{
a[i]=fpow(x,i);
}
for(int i=;i<=q;i++)
{
b[i]=fpow(y,i);
}
int cnt=;
for(int i=;i<=p;i++)
{
for(int k=;k<=q;k++)
{
if(a[i]+b[k]<=r&&a[i]+b[k]>=l)
sum[cnt++]=a[i]+b[k];
}
}
sort(sum,sum+cnt);
cnt=unique(sum,sum+cnt)-sum;
if(cnt==)
{
cout<<r-l+<<endl;
return ;
}
ll ans=max(sum[]-l,r-sum[cnt-]);
for(int i=;i<=cnt-;i++)
{
ans=max(ans,sum[i]-sum[i-]-);
}
cout<<ans<<endl;
return ;
}