HDU 4565 So Easy!（矩阵快速幂+向上取整）

题意：给出正整数a，b，n，m，求下列式子结果。 （0< a, m < 2¹⁵, (a-1)²< b < a², 0 < b, n < 2³¹） 题解：矩阵快速幂+向上取整 我们可以发现$(a+\sqrt{b}{)}^n$最终可以化为$A+B\sqrt{b}$，其中$A$、$B$均为正整数，所以我们只要求$A$、$B$： $$A_i+B_i\sqrt{b}=(A_{i-1}+B_{i-1}\sqrt{b})\ast (a+\sqrt{b})$$ 由上式可得递推关系，因此我们就可以构造转移矩阵： $$T=\left[\begin{array}{cc}a& b\\ 1& a\end{array}\right]$$ 初始矩阵为： $$ma=\left[\begin{array}{c}a(A)\\ 1(B)\end{array}\right]$$ 用矩阵快速幂求完之后，我们发现取模之后的$B$再✖一个根号数，再向上取整，结果肯定跟原式不同。

由题目条件$(a-1{)}^2<b<a^2$，$0<a-\sqrt{b}<1$，即$$0<(a-\sqrt{b}{)}^n<1$$ 由于上式依然可以化为$0<A-B\sqrt{b}<1$，所以我们可得$$A-1<B\sqrt{b}<A$$ 知道了这个小数整体范围，我们就可以对他进行精确的向上取整了。最后答案就是$2\ast A$。

记得特判n=1即可。

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<cmath> #include<vector> #include<fstream> #include<set> #include<map> #include<sstream> #include<iomanip> #define ll long long using namespace std; int a, b, n, m; //矩阵快速幂 struct matrix { ll mat[2][2]; matrix() { memset(mat, 0, sizeof(mat)); } matrix operator * (const matrix& b)const { matrix ans; for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { ans.mat[i][j] = 0; for (int k = 0; k < 2; k++) { ans.mat[i][j] = (ans.mat[i][j] + mat[i][k] * b.mat[k][j] % m + m) % m; } } } return ans; } }; matrix q_pow(matrix a, ll b) { matrix ans; memset(ans.mat, 0, sizeof(ans.mat)); for (int i = 0; i < 2; i++) ans.mat[i][i] = 1; while (b) { if (b & 1) ans = ans * a; b >>= 1; a = a * a; } return ans; } int main() { while (~scanf("%d%d%d%d", &a, &b, &n, &m)) { if (n == 1) { printf("%d\n", 2 * a % m); continue; } matrix ma; ma.mat[0][0] = a; ma.mat[0][1] = b; ma.mat[1][0] = 1; ma.mat[1][1] = a; ma = q_pow(ma, n - 1); int A = (ma.mat[0][0] * a + ma.mat[0][1]) % m; printf("%d\n", 2 * A % m); } return 0; }