小G的GCD

题目链接：nowcoder 217463

到主站看：https://blog.csdn.net/weixin_43346722/article/details/116243756

题目大意

问你 gcd(x,y) 用辗转相除法来求，如果限定 x,y 都小于一个值，那辗转相除法的递归最多要递归多少次。

思路

这道题给出了暴力程序，那我们就试着运行一下它，用它看看有什么规律。

然后你就从 0 开始试，你会发现答案是这样子的：（从 0 开始）
0,2,3,4,5,5,6,6,6,7,7,7,7,7,……

然后你会发现，除了 0，其它还挺有规律的，进过了一定的个数就比原来多了个 1，而且这个个数还在增加。
然后你可以看看每次的个数是多少（不算 0 了）：1,1,2,3,5,……

你会发现它很像斐波那契数列，然后试着跟着算一下，发现暴力答案跟你的答案一样。

那就可以开搞了。

（其实听说可以推理出来，但是我这种弱鸡肯定是不会的啦）

代码

#include<cstdio>
#include<iostream>
#define ll long long

using namespace std;

ll n, ans, a, b, c;

//根据题目给定代码进行打标找规律
//long long GCD(long long x, long long y) {
//     if (!y) return 1ll;
//     return GCD(y, x % y) + 1ll;
//}
//
//long long maxGCD(long long n) {
//     long long ans = 0ll;
//     for (long long i = 1; i <= n; i++)
//         for (long long j = 1; j <= n; j++)
//             ans = max(ans, GCD(i, j));
//     return ans;
// }

int main() {
    scanf("%lld", &n);
//    printf("%lld", maxGCD(n));

    if (n == 0) printf("0");//先搞前几位
    if (n == 1) printf("2");
    if (n == 2) printf("3");
    if (n == 3) printf("4");
    if (n > 3) {
        n -= 3;
        ans = 4;

        a = 1;
        b = 1;
        c = 2;

        while (c < n) {//根据打标找出的规律（斐波那契）来找答案
            ans++;
            n -= c;
            a = b;
            b = c;
            c = a + b;
        }

        printf("%lld", ans + (c == n));
    }

    return 0;
}

//打标找规律的草稿
/*
1 2//奇数行表示第一次出现这个答案（第二个数）n 是多少（第一个数）
1//偶数行表示之间相差了多少个数
2 3
1
3 4
2
5 5
3
8 6
5
13 7
8
21 8
13
34 9
*/