题目大意:给你一个数字n(n<=1e9) ,让你求一个能包含这个数的斐波那契数列的第一项a
和第二项b,找出b最小的那个。
帮我复习了一下扩展欧几里得。。。。
思路:a,b,a+b,a+2b……我们能枚举出50项内,每一项的a和b的数量,然后就是从后往前解
二元一次方程。 其实以a为第一项,b为第二项的斐波那切数列公式为,a[ i ]=f[ i – 1 ] * x+f[ i ]*y。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
ll fi[],se[],n,a,b,ans1,ans2,res1,res2;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==)
{
x=; y=;
return a;
}
else
{
ll gcd,t; gcd = exgcd(b,a%b,x,y);
t=x; x=y; y=t-(a/b)*y;
return gcd;
}
}
bool work(ll fi,ll se,ll n,int id)
{
if(fi>n || se>n) return false;
ll x,y,gcd=exgcd(fi,se,x,y);
if(n%gcd!=) return false;
ll g=n/gcd;
x=x*g; y=y*g;
ll change1=fi/gcd;
ll change2=se/gcd;
if(x<)
{
ll cnt=(-x)/change2;
x+=cnt*change2;
y-=cnt*change1;
if(x<)
{
x+=change2;
y-=change1;
}
if(y<) return false;
}
else if(y<)
{
ll cnt=(-y)/change1;
x-=cnt*change2;
y+=cnt*change1;
if(y<)
{
x-=change2;
y+=change1;
}
if(x<) return false;
}
if(x<=y)
{
ll cnt=(y-x)/(change1+change2);
x+=cnt*change2;
y-=cnt*change1;
if(x>y || y<)
{
x-=change2;
y+=change1;
}
}
else
{
ll cnt=(x-y)/(change1+change2);
x-=cnt*change2;
y+=cnt*change1;
if(x>y)
{
x-=change2;
y+=change1;
}
if(x< || y<) return false;
}
if(x< || y< || x>y) return false;
res1=x; res2=y;
return true;
}
int main()
{
ll x,y;
fi[]=;se[]=;fi[]=;se[]=;
for(int i=;i<=;i++)
{
fi[i]=fi[i-]+fi[i-];
se[i]=se[i-]+se[i-];
}
int T; scanf("%d",&T);
while(T--)
{
scanf("%I64d",&n);
ans1=ans2=inf;
for(int i=;i>=;i--)
{
if(work(fi[i],se[i],n,i))
{
if(res2<ans2)
{
ans2=res2;
ans1=res1;
}
else if(res2==ans2 && res1<ans1)
{
ans2=res2;
ans1=res1;
}
}
}
printf("%I64d %I64d\n",ans1,ans2);
}
return ;
}