内容简介:问题描述输入格式输入第一行包含两个整数b, m,第二行和第三行每行两个整数,为矩阵A。
问题描述
给定一个矩阵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求余。
输入格式
输入第一行包含两个整数b, m,第二行和第三行每行两个整数,为矩阵A。
输出格式
输出两行,每行两个整数,表示A^b%m的值。
样例输入
2 2
1 1
样例输出
1 0
分析:1.用快速幂的解法递归下去即可
2.按照题目测试数据,矩阵的0次方,应该为全部数字为0, 矩阵的1次方,矩阵不变~
#include <iostream> #include <vector> using namespace std; int m; vector<int> mul(vector<int> a, vector<int> b) { vector<int> ans(5); ans[1] = (a[1] * b[1] + a[2] * b[3]) % m; ans[2] = (a[1] * b[2] + a[2] * b[4]) % m; ans[3] = (a[3] * b[1] + a[4] * b[3]) % m; ans[4] = (a[3] * b[2] + a[4] * b[4]) % m; return ans; } vector<int> f(vector<int> v, int b) { vector<int> minn(5), nulln(5); minn[1] = minn[4] = 1; if (b == 0) { return mul(nulln, minn); } else if (b == 1) { return mul(v, minn); } else if (b % 2 == 0) { vector<int> t(5); t = f(v, b / 2); return mul(t, t); } else { return mul(f(v, b - 1), v); } } int main() { vector<int> v(5), ans; int b; cin >> b >> m; cin >> v[1] >> v[2] >> v[3] >> v[4]; ans = f(v, b); printf("%d %d\n%d %d\n", ans[1], ans[2], ans[3], ans[4]); return 0; }❤❤点击这里 -> 订阅PAT、蓝桥杯、GPLT天梯赛、LeetCode题解离线版❤❤
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 如何备战蓝桥杯拿到省一
- 蓝桥杯 ADV-126 算法提高 扫雷
- 蓝桥杯 ADV-133 算法提高 彩票
- 蓝桥杯 ALGO-112 算法训练 暗恋
- 蓝桥杯 算法训练 审美课 java
- 蓝桥杯 ADV-233 算法提高 队列操作
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Remote
Jason Fried、David Heinemeier Hansson / Crown Business / 2013-10-29 / CAD 26.95
The “work from home” phenomenon is thoroughly explored in this illuminating new book from bestselling 37signals founders Fried and Hansson, who point to the surging trend of employees working from hom......一起来看看 《Remote》 这本书的介绍吧!