c++ - 代码的最优解，使其可以执行最多 10^18 的计算

Question

Constraints 1≤T≤10^5 1≤N≤10^18

The Fibonacci sequence F0,F1,… is a special infinite sequence of non-negative integers, where F0=0, F1=1 and for each integer n≥2, Fn=Fn−1+Fn−2.

考虑前 N 个斐波那契数的最后一位十进制数字的序列 D，即 D=(F0%10,F1%10,…,FN−1%10)。现在，您应该执行以下过程:

设 D=(D1,D2,…,Dl)。 如果l=1，则过程结束。 创建一个新序列 E=(D2,D4,…,D2⌊l/2⌋)。换句话说，E 是通过从 D 中删除所有奇数索引元素而创建的序列。 将 D 更改为 E。

说明 示例情况 1:前 N 个斐波那契数为 (0,1,1,2,3,5,8,13,21)。序列D为(0,1,1,2,3,5,8,3,1)→(1,2,5,3)→(2,3)→(3)。

到目前为止我做了什么

    #include<iostream>
    #include<vector>
    using namespace std;
    #define m 10
void multiply(long long f[][2], long long g[][2])
{
    long long a = (f[0][0] * g[0][0] + f[0][1] * g[1][0]) % m;
    long long b = (f[0][0] * g[0][1] + f[0][1] * g[1][1]) % m;
    long long c = (f[1][0] * g[0][0] + f[1][1] * g[1][0]) % m;
    long long d = (f[1][0] * g[0][1] + f[1][1] * g[1][1]) % m;

    f[0][0] = a;
    f[0][1] = b;
    f[1][0] = c;
    f[1][1] = d;
}
void power(long long f[2][2], long long n)
{
    long long g[2][2] = { {1,1},{1,0} };
    if (n == 0 || n == 1)
        return;
    power(f, n / 2);
    multiply(f, f);

    if (n % 2 == 1)
        multiply(f, g);
}
long long fib(long long n)
{
    long long f[2][2] = { {1,1},{1,0} };
    if (n == 0)
        return 0;
    power(f, n - 1);
    return f[0][0] % m;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    unsigned int t;
    std::cin >> t;
    while (t--) {
        long long int td;
        std::cin >> td;
        vector<long long int> d;
        unsigned long long int temp;
        for (unsigned long long int i = 0;i < td;i++) {
            d.push_back(fib(i) % m);
        }
        if (d.size() == 1) {
            cout << d[0] << endl;
        }
        else if (d.size() == 2 || d.size() == 3) {
            cout << d[1] << endl;
        }
        else {
            vector<long long int> e;
            long long int si = d.size();
            while (si != 1) {
                for (long long i=1;i<si;i=i+2) {
                        e.push_back(d[i]);
                }
                d = e;
                e.clear();
                si = d.size();
            }
            cout << d[0] << " ";
        }
        d.clear();
    }
    return 0;
}

Answer 1

 #include<iostream>
 #include<vector>
 using namespace std;
 int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    // the last digits of the fibonnacci sequence repeat at 60.
    // let's just get them all
    int lastDigits[60];
    lastDigits[0] = 0;
    lastDigits[1] = 1;
    for (int i=2;i<60;i++) {
        lastDigits[i] = (lastDigits[i-2]+lastDigits[i-1]) % 10;
    }

    unsigned int t;
    std::cin >> t; //number of test cases
    while (t--) {
        long long int td;
        std::cin >> td;  //next case

        // after repeatedly removing even-indexed (zero-based) items, the
        // original index of the last remaining item will be the highest
        // 2^n - 1 that fits.  We can calculate this directly
        td >>= 1;
        td |= td>>32;
        td |= td>>16;
        td |= td>>8;
        td |= td>>4;
        td |= td>>2;
        td |= td>>1;

        cout << lastDigits[(int)(td%60)] << endl;
    }
    return 0;
}