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