这道题目可以先转化:
令f(1) = 5+2√6
f(2) = f(1)*(5+2√6)
...
f(n) = f(n-1)*(5+2√6)
f(n) = f(n-1)*(10-(5-2√6)) = 10*f(n-1)-(5-2√6)f(n-1) = 10*f(n-1) - 10/(5+2√6) f(n-1) = 10*f(n-1) - 10/(5+2√6) * (5+2√6)f(n-2)
= 10*f(n-1) - f(n-2)
那么就可以写成矩阵相乘的形式了
(f(n) , f(n-1)) = (f(n-1) , f(n-2)) (10 , 1
-1 , 0)
但这里2^x+1还是很大，这里就用到广义斐波那契数列找循环节的思想
循环节长度 = (mod-1)*(mod+1)
具体证明可以参考这里: 广义斐波那契数列
那么只要求出对模循环节后的长度进行幂运算就行了
但这里f(i)都是带根号的小数 , 这里就选择用近似的整数代替
5+2√6 = 9.89...
f(0) = (5+2√6)^0 = 1
f(1) = (5+2√6)^1 = 5+2√6
/*囧 想了半天我还是不知道为什么f(0)用2代替 ， f(1)用10代替就一定保证之后取到的都是上顶*/
#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
int n,q;
ll MOD;
struct Matrix{
int m[][];
void init(){m[][]=m[][]=;m[][]=m[][]=;}
Matrix operator*(const Matrix &p) const{
Matrix ret;
for(int i= ; i< ; i++)
for(int j= ; j< ; j++){
ret.m[i][j]=;
for(int k= ; k< ; k++){
ret.m[i][j] = (ret.m[i][j]+((ll)m[i][k]*p.m[k][j])%MOD)%MOD;
}
}
return ret;
}
}; int qpow(int b)
{
ll ret= , a=;
while(b){
if(b&) ret = ret*a%MOD;
a = a*a%MOD;
b>>=;
}
return ret;
} Matrix qpow(Matrix a , int b)
{
Matrix ret;
ret.init();
while(b){
if(b&) ret = ret*a;
a = a*a;
b>>=;
}
return ret;
} int main()
{
// freopen("a.in" , "r" , stdin);
int T , cas=;
scanf("%d" , &T);
while(T--)
{
scanf("%d%d" , &n , &q);
MOD = (q-)*(q+);
n = qpow(n);
MOD = q;
Matrix a;
a.m[][]= , a.m[][]=- , a.m[][]= , a.m[][]=;
a = qpow(a , n);
ll val = (ll)*a.m[][]+(ll)*a.m[][];
val = ((val%MOD)+MOD)%MOD;
printf("Case #%d: %I64d\n" , ++cas , (val+MOD-)%MOD);
}
return ;
}