盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 5451 Best Solver(数学+广义Fibonacci循环节+矩阵快速幂)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5451

题意

计算(5+2sqrt(6))^(1+2^x) 向下取整 mod m 其中x为int范围,m为质数

思路

http://blog.csdn.net/crazy______/article/details/9021169
http://blog.csdn.net/ACdreamers/article/details/25616461

另 fn = (a+sqrt(b))^n + (a-sqrt(b))^n
化简得到fn+1 = 2a*fn - fn-1
其中0<(a-sqrt(b))^n<1 所以可以用矩阵快速幂来求。
但是x很大, 所以要用到循环节。即求广义Fibonacci数列循环节。这里直接用(p+1)(p-1)来做循环节

官方题解里提到(p^2-p)(p^2-1)是一个通用循环节

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int maxn = 2;
const int maxm = 2;
ll mod;
struct Matrix {
int n, m;
ll a[maxn][maxm];
void clear() {
n = m = 0;
memset(a, 0, sizeof(a));
}
Matrix operator * (const Matrix &b) const { //实现矩阵乘法
Matrix tmp;
tmp.n = n;
tmp.m = b.m;
for (int i = 0; i < n; i++)
for (int j = 0; j < b.m; j++) tmp.a[i][j] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (!a[i][j]) continue;
for (int k = 0; k < b.m; k++)
tmp.a[i][k] += a[i][j] * b.a[j][k], tmp.a[i][k] %= mod;
}
return tmp;
}
void Copy(const Matrix &b) {
n = b.n, m = b.m;
for (int i = 0; i < n; i++)
for(int j = 0; j < m; j++) a[i][j] = b.a[i][j];
}
void unit(int sz) {
n = m = sz;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) a[i][j] = 0;
a[i][i] = 1;
}
}
};
Matrix A, B;
Matrix Matrix_pow(Matrix A, ll k, ll mod) { //矩阵快速幂
Matrix res;
res.clear();
res.n = res.m = 2;
for (int i = 0; i < 2; i++) res.a[i][i] = 1;
while(k) {
if (k & 1) res.Copy(A * res);
k >>= 1;
A.Copy(A * A);
}
return res;
}
ll pow_mod(ll a, ll n, ll p) {
ll res = 1;
while (n) {
if (n & 1) res = res * a % p;
n >>= 1;
a = a * a % p;
}
return res;
}
int x, m;
void init() {
A.a[0][0] = 10;
A.a[0][1] = -1;
A.a[1][0] = 1;
A.a[1][1] = 0;
A.n = A.m = 2;
}
int work() {
mod = m * m - 1;
ll k = pow_mod(2, x, mod);
mod = m;
Matrix ans = Matrix_pow(A, k, mod);
ll res = (ans.a[0][0] * 10 + ans.a[0][1] * 2) % mod;
res = (res - 1 + mod) % mod;
return res;
}
int main () {
init();
int t, cas = 1;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &x, &m);
printf("Case #%d: %d\n", cas++, work());
}
return 0;
}