问题描述
给定一个矩阵A,一个非负整数b和一个正整数m，求A的b次方除m的余数。
其中一个nxn的矩阵除m的余数得到的仍是一个nxn的矩阵，这个矩阵的每一个元素是原矩阵对应位置上的数除m的余数。
要计算这个问题，可以将A连乘b次，每次都对m求余，但这种方法特别慢，当b较大时无法使用。下面给出一种较快的算法(用A^b表示A的b次方)：
若b=0，则A^b%m=I%m。其中I表示单位矩阵。
若b为偶数，则A^b%m=(A^(b/2)%m)^2%m，即先把A乘b/2次方对m求余，然后再平方后对m求余。
若b为奇数，则A^b%m=(A^(b-1)%m)*a%m，即先求A乘b-1次方对m求余，然后再乘A后对m求余。
这种方法速度较快，请使用这种方法计算A^b%m，其中A是一个2×2的矩阵，m不大于10000。
输入格式
输入第一行包含两个整数b, m，第二行和第三行每行两个整数，为矩阵A。
输出格式
输出两行，每行两个整数，表示A^b%m的值。
样例输入
2 2
1 1
0 1
样例输出
1 0
0 1
分析：1.按照题目要求即可，和快速幂算法类似
2.注意 当相乘次数为0时，输出单位矩阵（题目要求）,（但是后台测试数据给的是0 0 0 0!）
|
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 |
#include <iostream> #include <vector> using namespace std; vector<int> f(vector<int> v, int k, int m) { vector<int> ans(5); if (k == 0) { ans[1] = ans[4] = 1; ans[2] = ans[3] = 0; } else { if (k % 2 == 0) { vector<int> t = f(v, k / 2, m); ans[1] = (t[1] * t[1] + t[2] * t[3]) % m; ans[2] = (t[1] * t[2] + t[2] * t[4]) % m; ans[3] = (t[3] * t[1] + t[4] * t[3]) % m; ans[4] = (t[3] * t[2] + t[4] * t[4]) % m; } else { vector<int> t = f(v, k - 1, m); ans[1] = (t[1] * v[1] + t[2] * v[3]) % m; ans[2] = (t[1] * v[2] + t[2] * v[4]) % m; ans[3] = (t[3] * v[1] + t[4] * v[3]) % m; ans[4] = (t[3] * v[2] + t[4] * v[4]) % m; } } return ans; } int main() { int k, m, a, b, c, d; vector<int> v(5), ans; cin >> k >> m >> v[1] >> v[2] >> v[3] >> v[4]; ans = f(v, k, m); printf("%d %d\n%d %d\n", ans[1], ans[2], ans[3], ans[4]); return 0; } |
❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼
❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼
❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版
