感谢这道题让我复习了一遍线代，还学习了一些奇奇怪怪的数论。
令
二项展开以后根号部分抵消了
显然有
所以要求的答案是
如果n比较小的话，可以直接对二项式快速幂，但是这题n很大
这个问题和矩阵的特征值以及数列递推有奇怪的联系
广义的fibonacci数列的形式如下
写成矩阵形式就是
有一个奇怪的结论：
其中lambda1，lambda2是递推矩阵的特征值，此处只讨论lambda1!=lambda2的情况。
这个奇怪的结论其实很容易证明，
根据以上结果，利用矩阵的数乘和分配律然后归纳就可以完整得到结论
令lambda1=p，lambda2=q，可以求出a和b，答案就在递推的第n项
然后通过找循环节减小n
m是素数时一般的做法：
费马小定理和欧拉准则不明觉厉。。。
此题所有的m循环节都小，直接暴力，然后记忆化
lambda1!=lambda2，所以A一定可以对角化，而A^n就可以表示为
对应特征值
并且有
所以对A矩阵快速幂以后算出迹减1就是答案
#includeusing namespace std;typedef long long ll;struct Matrix{ int e[2][2]; int* operator[](int p){ return e[p]; }};ll Mod;Matrix operator *(Matrix &A, Matrix &B){ Matrix R; for(int i = 0; i < 2; i++){ for(int j = 0; j < 2; j++){ R[i][j] = 0; for(int k = 0; k < 2; k++){ R[i][j] = (R[i][j] + (ll)A[i][k]*B[k][j]+Mod)%Mod; } } } return R;}Matrix Matrix_pow(Matrix A,ll p){ Matrix R; for(int i = 0; i < 2; i++){ for(int j = 0; j < 2; j++){ R[i][j] = i==j?1:0; } } while(p){ if(p&1) R = R*A; A = A*A; p>>=1; } return R;}ll qPow(ll a,ll p,ll mod){ ll ret = 1; while(p){ if(p&1) ret = (ret*a)%mod; a = (a*a)%mod; p >>= 1; } return ret;}const int maxm = 46337+5;int r[maxm],f[maxm];int main(){ //freopen("in.txt","r",stdin); int T, kas = 0; scanf("%d",&T); while(T--){ ll x; scanf("%I64d%I64d",&x,&Mod); if(!r[Mod]){ f[0] = 2; f[1] = 10; for(int i = 2; ;i++){ f[i] = (10LL*f[i-1]-f[i-2]+Mod)%Mod; if(f[i] == f[1] && f[i-1] == f[0]){ r[Mod] = i-1; break; } } } Matrix A; A[0][0] = 10%Mod; A[0][1] = Mod-1; A[1][0] = 1; A[1][1] = 0; auto ans = Matrix_pow(A,(qPow(2,x,r[Mod])+1)%r[Mod]); printf("Case #%d: %d\n",++kas,(ans[0][0]+ans[1][1]+Mod-1)%Mod); } return 0;}