萌新求助斐波那契 97pts

#include <bits/stdc++.h>
#define umap unordered_map
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

string S;
ll MOD;

const int L = 2;
struct Matrix {
    ll M[L+1][L+1];
    ll *operator[](int p) {
        return M[p];
    }
    void clear() {
        memset(M, 0, sizeof M);
    }
    void reset() {
        clear();
        for (int i = 1; i <= L; i++)
            M[i][i] = 1;
    }
    Matrix friend operator*(Matrix A, Matrix B) {
        Matrix C; C.clear();
        for (int i = 1; i <= L; i++)
            for (int k = 1; k <= L; k++)
                for (int j = 1; j <= L; j++)
                    (C[i][j] += A[i][k] * B[k][j] % MOD) %= MOD;
        return C;
    }
};

const ll MAXN = 6 * (1ll << 31);
const ll SQRT = 113511 + 1; // sqrt(MAXN) + 1
namespace qqpow {
    Matrix q[SQRT + 5], r[SQRT + 5];
    void init(Matrix a) {
        r[0].reset();
        for (int i = 1; i <= SQRT; i++)
            r[i] = r[i-1] * a;
        q[0].reset();
        for (int i = 1; i <= SQRT; i++)
            q[i] = q[i-1] * r[SQRT];
    }
    Matrix qpow(ll b) {
        return q[b / SQRT] * r[b % SQRT];
    }
}
using qqpow::qpow;
ll fib(ll n) {
    return qpow(n-1)[1][1];
}

void init() {
    Matrix A;
    A[1][1] = 1; A[1][2] = 1;
    A[2][1] = 1; A[2][2] = 0;
    qqpow::init(A);
}

int main() { ios::sync_with_stdio(0); cin.tie(0);
    cin >> S >> MOD;
    if (MOD == 1) {
        cout << 0 << endl;
        return 0;
    }
    init();

    mt19937_64 rnd(time(0));
    umap<ull, ll> mp;
    ll pi;
    while (true) {
        ll x = rnd() % MAXN;
        ull y = (ull)fib(x) << 32 | fib(x+1);
        if (mp.find(y) != mp.end()) {
            pi = abs(x - mp[y]);
            break;
        }
        mp[y] = x;
    }
    ll n = 0;
    for (auto c : S)
        n = (n * 10 + (c - '0')) % pi;
    cout << fib(n) << endl;
    return 0;
}