小G的GCD

题目描述

小G刚学习完辗转相除法求GCD，现在他想探究一下辗转相除具体的次数。
然后写出了如下代码：

long long GCD(long long x, long long y) {
     if (!y) return 1ll;
     return GCD(y, x % y) + 1ll;
}

现在小G很好奇一个问题，他想求一下maxGCD
小G接着写出了以下代码：

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;
 }

但是这个代码太慢了，小G会给出一个 $n$ ，希望你帮他快速求出答案。

这道题正解在考试的时候没有写出来，但是找找规律就可以过了。

我们写一个这样的代码：

#include <bits/stdc++.h>
using namespace std;
#define MAXN 105
long long fib[MAXN];
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()
{
    long long n;
    while(cin >> n)
        cout << maxGCD(n) << " ";
    return 0;
}

输入：

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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

然后我们会发现输出的是：

2 3 4 4 5 5 5 6 6 6 6 6 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11

我们会发现：

答案什么数：2  3  4  5  6  7  8  9  10
出现了几次: 1  1  2  3  5  8  11 19 30

！！！
这……这不就是斐波那契数列吗？
于是我们再来看 $10^{18}$ 范围内的斐波那契数有多少个：

#include <bits/stdc++.h>
using namespace std;
#define MAXN 105
long long fib[MAXN];
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()
{
    long long x = 1, y = 1, z, tot = 1, i = 0;
    while(tot < 1000000000000000000)
    {
        i++;
        tot += x + y;
        z = x + y;
        x = y;
        y = z;
    }
    printf("%lld %lld\n", i, tot);
    return 0;
}

我们发现在前80个斐波那契数的和轻轻松松就可以超过 $10^{18}$ ，所以我们的程序就写得出来了：

#include <bits/stdc++.h>
using namespace std;
#define MAXN 105
long long fib[MAXN];
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()
{
    long long n;
    cin >> n;
    int ans = 0;
    fib[0] = 1;
    fib[1] = 1;
    for(int i = 2; i <= 76; i++)
        fib[i] = fib[i - 1] + fib[i - 2];
    ans = 2;
    for(int i = 0; i <= 76; i++)
    {
        if(n > fib[i])
        {
            n -= fib[i];
            ans++;
        }
        else
        {
            printf("%d\n", ans);
            return 0;
        }
    }
    return 0;
}

都看到这儿了，就点个赞吧~

~~（牛币+10086001）~~

C 小G的GCD

小G的GCD

题目描述