533
URAL 1133 二分
給出廣義斐波那契數列的任意兩項，讓求這個斐波那契數列的其他項。
這題解方程的話精度不夠所以二分求出f[a+1]這一項的值。二分的時候如果超範圍直接跳出。再通過f[a]與f[a+1]求出任意一項。寫得好挫啊。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int judge(long long x,long long a,long long b,long long fa,long long fb)
{
long long a1=fa,a2=x,a3;
for(int i=a+2; i<=b; i++)
{
a3=a1+a2;
if(a3>2e9)return 1;
if(a3<-2e9)return -1;
a1=a2,a2=a3;
}
if(a3==fb)return 0;
if(a3>fb)return 1;
if(a3<fb)return -1;
}
long long getf(long long a,long long fa,long long b,long long fb)
{
if(b-a==1)
{
return fb;
}
long long l=-2e9,r=2e9,mid;
while(l<=r)
{
mid=(l+r)>>1;
int tem=judge(mid,a,b,fa,fb);
if(tem==0)
return mid;
else if(tem==1)
r=mid-1;
else l=mid+1;
}
return mid;
}
int main()
{
long long a,b,fa,fb,n;
cin>>a>>fa>>b>>fb>>n;
if(a>b)swap(a,b),swap(fa,fb);
long long f=getf(a,fa,b,fb);
if(n==a) cout<<fa<<endl;
else if(n==a+1) cout<<f<<endl;
else if(n>a+1)
{
long long a1=fa,a2=f,a3;
for(int i=a+2; i<=n; i++)
{
a3=a1+a2;
a1=a2,a2=a3;
}
cout<<a3<<endl;
}
else if(n<a)
{
long long a1=f,a2=fa,a3;
for(int i=a+1; i>=n; i--)
{
a3=a1-a2;
a1=a2,a2=a3;
}
cout<<a3<<endl;
}
return 0;
}
最後更新：2017-04-03 15:22:11