题意:有式子y=(5+26)1+2xy=(5+2\sqrt6)^{1+2^x}.
给定 xxMM (0x<2320 \leq x < 2^{32}) 求y(x)y(x)的整数部分modmod MM的值是多少(向下取整)

推矩阵资料:http://blog.csdn.net/crazy______/article/details/9021169
广义斐波那契循环节:http://blog.csdn.net/acdreamers/article/details/25616461
构造类斐波那契数列矩阵:http://blog.csdn.net/acdreamers/article/details/8994222

。。真是。。神。。
可以根据式子推出矩阵 f(n+1)=10*f(n)-f(n-1)
注意f(1)=10 f(2)=2

//author: CHC
//First Edit Time: 2015-09-20 20:31
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+4;
const int MAXM=1e+5;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
const int N = 2;
void matric_mul(LL A[][N],LL B[][N],LL C[][N],LL mod){
LL tmp[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
tmp[i][j]=0;
for(int k=0;k<N;k++){
tmp[i][j]=((tmp[i][j]+A[i][k]*B[k][j])%mod+mod)%mod;
}
}
}
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
C[i][j]=tmp[i][j];
}
}
}
LL q_pow(LL n,LL mod){
LL tmp[][N]={{0,-1},{1,10}};
LL ans[N][N];
memset(ans,0,sizeof(ans));
for(int i=0;i<N;i++)ans[i][i]=1;
while(n){
if(n&1)matric_mul(ans,tmp,ans,mod);
n>>=1;
matric_mul(tmp,tmp,tmp,mod);
}
//printf("%I64d %I64d\n%I64d %I64d\n",ans[0][0],ans[0][1],ans[1][0],ans[1][1]);
//puts("");
//printf("%I64d %I64d\n",ans[1][1],ans[0][1]);
//return ans[1][1]%mod;
return ((((ans[1][1]*10)%mod+mod)%mod+((ans[0][1]*2)%mod+mod)%mod)%mod+mod)%mod;
}
LL q_pow1(LL base,LL n,LL mod){
LL ans=1;
while(n){
if(n&1)ans=ans*base%mod;
n>>=1;
base=base*base%mod;
}
return ans;
}
int main()
{
int T,cas=0;
scanf("%d",&T);
while(T--){
LL x;
int mod;
scanf("%I64d%d",&x,&mod);
LL p=(LL)(mod+1)*(mod-1);
LL r=q_pow1(2,x,p);
//printf("r:%I64d p:%I64d\n",r,p);
LL res=q_pow(r,mod);
//printf("%I64d\n",res);
printf("Case #%d: ",++cas);
if(!res){
printf("%d\n",mod-1);
}
else {
printf("%I64d\n",res-1);
}
//printf("%I64d\n",q_pow(x,mod));
//LL r=q_pow1(2LL,(LL)x,(LL)(mod-1)*(mod+1));
//printf("%I64d\n",q_pow(r,(LL)mod));
}
return 0;
}