The so-called best problem solver can easily solve this problem, with his/her childhood sweetheart.
It is known that y=(5+2√6)^(1+2^x).
For a given integer x (0≤x<2^32) and a given prime number M (M≤46337), print [y]%M. ([y] means the integer part of y)
Input
An integer T (1<T≤1000), indicating there are T test cases.
Following are TT lines, each containing two integers xx and MM, as introduced above.
Output
The output contains exactly TT lines.
Each line contains an integer representing [y]%M[y]%M.
Sample Input
7 0 46337 1 46337 3 46337 1 46337 21 46337 321 46337 4321 46337
Sample Output
Case #1: 97 Case #2: 969 Case #3: 16537 Case #4: 969 Case #5: 40453 Case #6: 10211 Case #7: 17947
思路：（参考博客）
如这种a+bsqrt(c)的n次方的，一般最后结果形式还是a+bsqrt(c),所以可以构造出矩阵使用矩阵快速幂，不过这个矩阵的乘方是2^n，n=1e9，所以这里想到了找循环节，广义斐波那契数列的循环节是(MOD-1)*(MOD+1)，因此可以用这个来减小指数。不过这里要求是向下取整然后再取模，取模和取整是不满足交换的，因此这里需要消除根号的影响，这里就可以考虑5-2sqrt(6),这个数是一个小于1的数其n次方也一定小于1，5+2sqrt(6)的n次方，可以写成a+b*sqrt(c)+(a-b*sqrt(c))-(a-b*sqrt(c))=2*a-(a-b*sqrt(c)),对上面这个式子向下取整，(a-b*sqrt(c))这个是个小于1的数，2*a是个整数，因此向下取整可以后可以写成2*a-1。然后对其取模就可以。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cctype>
#include<map>
using namespace std;
typedef long long ll;
int M;
struct node{ll m[2][2];void clear(){memset(m,0,sizeof(m));}void one(){memset(m,0,sizeof(m));m[0][0]=1;m[1][1]=1;}
};
struct nod{ll a, b, c, d;
};
node mul(node a,node b){node t;t.clear();for(int i=0;i<2;i++){for(int j=0;j<2;j++){for(int k=0;k<2;k++){t.m[i][j]+=a.m[i][k]*b.m[k][j];t.m[i][j]%=M; }}}return t;
}
node ksm(node a,ll b){node t;t.one();while(b){if(b&1){t=mul(t,a); } a=mul(a,a);b>>=1;}return t;
}
map<string,int> mp;
map<int,string> mp1;
int isprime(int x){int t=sqrt(x);for(int i=2;i<=t;i++){if(x%i==0)return 0;}return 1;
}ll Euler(ll n)
{ll ret=n; for(ll i=2;i*i<=n;i++)if(n%i==0){ret=ret/i*(i-1);while(n%i==0)n/=i;}if(n>1)ret=ret/n*(n-1);return ret;
}
ll qsm(ll a,ll b,ll p){ll t=1;while(b){if(b&1){t=(t*a)%p;} a=(a*a)%p;b>>=1;}return t;
}
void add(string &ss,ll a,ll len){if(len==0) return ; add(ss,a/10,len-1);ss+='0'+(a%10);
}
int len(ll x){ll t=10,i=1;while(x>=t){t*=10;i++;}return i;
}
int main()
{int t;scanf("%d",&t);int cas=1;while(t--){mp.clear();mp1.clear();ll x;scanf("%lld%d",&x,&M);node a,b;a.one();b.clear();b.m[0][0]=5;b.m[0][1]=12;b.m[1][0]=2;b.m[1][1]=5;a=ksm(b,qsm(2,x,(M-1)*(M+1)));ll res=5*a.m[0][0]+2*a.m[0][1];printf("Case #%d: %lld\n",cas++,(2*res-1)%M);}return 0;
}