没有意识到循环节最大是M^2，用域Z_M下二阶可逆矩阵群的最大循环节(M^2-1)*(M^2-M)来做，考虑大数乘法，矩阵乘法，做到吐血。将代码贴在下方留作纪念。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define rep(i,a,b) for(int i=a;i<=b;++i) 4 #define ms(arr,a) memset(arr,a,sizeof arr) 5 long long P; 6 long long M; 7 long long x; 8 long long modM(long long x) 9 { 10 if(x<0)return x%M+M; 11 else return x%M; 12 } 13 struct matrix 14 { 15 long long a,b,c,d; 16 matrix(){} 17 matrix(long long m,long long n,long long p,long long q):a(m),b(n),c(p),d(q){} 18 matrix(long long x):a(x),b(0),c(0),d(x){} 19 }; 20 matrix solve(matrix A,matrix B) 21 { 22 matrix ret; 23 ret.a=modM(A.a*B.a+A.b*B.c); 24 ret.b=modM(A.a*B.b+A.b*B.d); 25 ret.c=modM(A.c*B.a+A.d*B.c); 26 ret.d=modM(A.c*B.b+A.d*B.d); 27 return ret; 28 } 29 long long solve(long long x,long long y) 30 { 31 long long ret=0; 32 while(x) 33 { 34 if(x&1)ret=(ret+y)%P; 35 y=(2*y)%P; 36 x>>=1; 37 } 38 return ret; 39 } 40 template<typename T> 41 T quick_pow(T a,long long n) 42 { 43 T ret(1); 44 while(n) 45 { 46 if(n&1)ret=solve(ret,a); 47 a=solve(a,a); 48 n>>=1; 49 } 50 return ret; 51 } 52 int main() 53 { 54 int T;scanf("%d",&T); 55 rep(Case,1,T) 56 { 57 scanf("%lld%lld",&x,&M); 58 P=(M*M-1)*(M*M-M); 59 long long N=(quick_pow(2LL,x)+1)%P; 60 //printf("%lld ",N); 61 matrix tmp=(matrix){10,-1,1,0}; 62 tmp=quick_pow(tmp,N); 63 printf("Case #%d: %lld ",Case,modM(tmp.c*10+tmp.d*2-1)); 64 } 65 }