逆用辗转相除法可以发现结果与斐波那契数列有关

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    vector<unsigned long long> fib(84);
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i < 84; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    while (T--) {
        int n;
        cin >> n;
        if (n == 0) {
            cout << 1 << '\n';
        } else {
            cout << fib[n + 3] << '\n';
        }
    }
    return 0;
}cp