SP8547 MAIN74 - Euclids algorithm revisited 题解

题目链接：https://www.luogu.com.cn/problem/SP8547

题意：

我们经常用大名鼎鼎的欧几里得算法（辗转相除法）来计算两个数的最大公约数。

对于 \((7,3)\)，上述代码中的 while 循环将运行两次： \((7,3)\rightarrow(3,1)\rightarrow(1,0)\)

现在给你一个整数 \(N(0\le N\le10^{18})\)，你需要找出和最小的二元组 \((a,b)\) 满足 \((a\ge b\ge0)\) 且上面提到的代码 while 循环将恰好运行 \(N\) 次

原文：

Consider the famous euclid algoithm to calculate the GCD of two integers \((a, b)\):
int gcd(int a, int b)
{
    while (b != 0)
    {
        int temp = a;
        a = b;
        b = temp % b;
    }
    return a;
}
for input \((7, 3)\) the 'while' loop will run \(2\) times as follows: \((7, 3) \Rightarrow (3, 1) \Rightarrow (1, 0)\)

Now given an integer \(N\) you have to find the smallest possible sum of two non-negative integers \(a,b (a \ge b)\) such that the while loop in the above mentioned function for \((a, b)\) will run exactly \(N\) times.

输入格式：

First line of input contains \(T (1 \le T \le 50)\) the number of test cases. Each of the following \(T\) lines contains an integer \(N (0 \le N \le 10^{18})\).

输出格式：

For each test case print the required answer modulo \(10^9 + 7\) in a seperate line.

这种题不是结论题就是观察题，总之最好的方法就是打个表。

然后你会发现这题跟斐波那契数列有关，那么为什么呢？

首先我们需要一个结论：斐波那契数列的任意相邻两项互质。

证明： \[ \operatorname{gcd}\left(f_k, f_{k-1}\right)=\operatorname{gcd}\left(f_{k-1}, f_k-f_{k-1}\right)=\operatorname{gcd}\left(f_{k-1}, f_{k-2}\right)=\cdots=\operatorname{gcd}\left(f_2, f_1\right)=1 \] 诶，很🐮b，这玩意就是这道题的结论。这玩意不打表真的想不到。

时间复杂度 \(\mathcal{O}(T\log N)\)

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
typedef vector< vector<int> > mat;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)())

mat mul(mat &A,mat &B)
{
    int n = A.size(), m = A[0].size(), p = B[0].size();
    mat C(n, vector<int>(p));
    for(int k = 0; k < m; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < p; j++)
                add(C[i][j], A[i][k] * B[k][j] % mod);
    return C;
}
mat qpow(mat A, int k)
{
    int n = max(A.size(), A[0].size());
    mat B(n, vector<int>(n));
    for(int i = 0; i < n; i++) B[i][i] = 1;
    for(; k; k >>= 1) {
        if(k & 1) { B = mul(B, A); } A = mul(A,A);
    } return B;
}
void solve()
{
    int n; cin >> n;
    if(n < 2) return cout << 2 * n << '\n', void(0); else { n += 3; }
    mat A(2, vector<int>(2)), B(2, vector<int>(1));
    A[0][0] = A[0][1] = A[1][0] = 1; B[0][0] = B[1][0] = 1;
    A = qpow(A, n - 2); A = mul(A, B); cout << A[0][0] << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}