C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 408K, 提交时间: 2023-06-24 05:17:46

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m,i,j,k;

void mul(ll a[][2],ll b[][2],ll c[][2]){
    ll t[][2] = {{0,0},{0,0}};
    for( i=0;i<2;i++)
        for(j=0;j<2;j++)
            for(k=0;k<2;k++)
            t[i][j] = (t[i][j] + a[i][k]%m*b[k][j]%m)%m;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            c[i][j] = t[i][j];
}
int main(){
    ll res[2][2] = {{1,0},{0,1}}, a[2][2] = {{0,1},{1,1}}, n;
    cin>>n>>m;
    while(n){
        if(n&1)
            mul(res,a,res);
        mul(a,a,a);
        n/=2;
    }
    cout<<res[0][1]%m<<endl;
}