斐波那契

发表于 更新于 分类于
  • 思路：根据数据，我们能发现，任意两个斐波纳契数做差会得到另一个斐波纳契数。那我们先根据数据范围打一个60项斐波纳契数列表，然后写一个函数。函数通过递归，不断把较大值减去在数列中第一个小于它的数，知道两数相等或其中一个数为1。
  • 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define gc getchar()
    #define ll long long
    using namespace std;
    ll sc() {
    	ll xx=0,ff=1; char cch;
    	while(cch<'0'|| cch>'9') {
    		if(cch=='-') ff=-ff; cch=gc;
    	}
    	while(cch>='0'&& cch<='9') {
    		xx=xx*10+(cch-48); cch=gc;
    	}
    	return xx*ff;
    }
    long long a[100];
    int n;
    namespace DY {
    	inline long long check(ll x,ll y) {
    		if(x<y) swap(x,y);
    		if(x==y) return x;
    		int now=lower_bound(a,a+61,x)-a;
    		return check(y,x-a[now-1]);
    	}
    	void main() {
    		a[1]=a[2]=1;
    		for(register int i=3; i<=60; i++)
    			a[i]=a[i-1]+a[i-2];
    		n=sc();
    		while(n--) {
    			ll x=sc(),y=sc();
    			printf("%lld\n",check(x,y));
    		}
    	}
    };
    int main() {
    	DY::main();
    	return 0;
    }