Problem Description
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 T lines, each containing two integers x and M , as introduced above.
Following are T lines, each containing two integers x and M , as introduced above.
Output
The output contains exactly T lines.
Each line contains an integer representing [y]%M .
Each line contains an integer representing [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
题目大意就是求那个式子y=(5+2√6)^(1+2^x)。
考虑(5+2√6)^n和(5-2√6)^n；
分别设为A和B，
自然A*B=1
考虑A+B，发现奇数次幂的根号消掉了，于是是个整数。
由因为A>1,自然B<1所以说A的小数部分就是1-B,所以A的整数部分就是A+B-1。
于是就是求A+B，便能得到结果。
而这个式子跟特征根求解的一次线性递推式的结果很像。
于是考虑x^2+bx+c=0这个特征方程，跟为5+2√6和5-2√6。
得b=-10,c=1。
于是递推式为f(n+2)=10f(n+1)-f(n)。
然后本地打表发现，不管模范围内的任何素数，这个序列的循环节都不是很大。
于是考虑直接暴力循环节，不过记忆化下来。
然后就是考虑2^x模循环节的结果即可，这个用快速幂。
复杂度是O(r+logx),其中r为循环节大小。
题解中通过结论 (p^2- p)(p^2-1)为循环节使用矩阵快速幂.
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#define LL long long using namespace std; const int maxM = ;
int x, m, r[maxM], f[maxM]; void init()
{
if (r[m] != -)
return;
f[] = %m;
f[] = %m;
for (int i = ;; ++i)
{
f[i] = ((*f[i-]-f[i-])%m+m)%m;
if (f[i-] == f[] && f[i] == f[])
{
r[m] = i-;
break;
}
}
} //快速幂m^n
int quickPow(LL x, int n, int mm)
{
int a = ;
while (n)
{
a *= n& ? x : ;
a %= mm;
n >>= ;
x *= x;
x %= mm;
}
return a;
} void work()
{
int k, ans;
k = quickPow(, x, r[m]);
k = (k+)%r[m];
f[] = %m;
f[] = %m;
for (int i = ; i <= k; ++i)
f[i] = ((*f[i-]-f[i-])%m+m)%m;
ans = (f[k]-+m)%m;
printf("%d\n", ans);
} int main()
{
//freopen("test.in", "r", stdin);
memset(r, -, sizeof(r));
int T;
scanf("%d", &T);
for (int times = ; times < T; ++times)
{
printf("Case #%d: ", times+);
scanf("%d%d", &x, &m);
init();
work();
}
return ;
}