1//整数的快速幂 m^n % k 的快速幂:
long long quickpow(long long m , long long n , long long k){
long long ans = 1;
while(n){
if(n&1)//如果n是奇数
ans = (ans * m) % k;
n = n >> 1;//位运算“右移1类似除2”
m = (m * m) % k;
}
return ans;
}
2矩阵快速幂:
定义一个矩阵类,例如求(A^n)%mod
class Matrix {
public:
long long m[MAXN][MAXN];
//二维数组存放矩阵
Matrix(){}
//对数组的初始化
void init(long long num[MAXN][MAXN]){
for(int i = 0 ; i < MAXN ; i++){
for(int j = 0 ; j < MAXN ; j++){
m[i][j] = num[i][j];
}
}
}
//重载矩阵的乘法运算
friend Matrix operator*(Matrix &m1 ,Matrix &m2) {
int i, j, k;
Matrix temp;
for (i = 0; i < MAXN; i++) {
for (j = 0; j < MAXN; j++) {
temp.m[i][j] = 0;
for(k = 0 ; k < MAXN ; k++)
temp.m[i][j] += (m1.m[i][k] * m2.m[k][j])%mod
temp.m[i][j] %= mod;
//注意每一步都进行取模
}
}
return temp;
}
//矩阵的快速幂
friend Matrix quickpow(Matrix &M , long long n){
Matrix tempans;
//初始化为单位矩阵
//初始化
for(int i = 0 ; i < MAXN ; i++){
for(int j = 0 ; j < MAXN ; j++){
if(i == j)
tempans.m[i][j] = 1;
else
tempans.m[i][j] = 0;
}
}
//快速幂(类似整数)
while(n){
if(n & 1)
tempans = tempans * M;
//已经重载了*
n = n >> 1;
M = M * M;
}
return tempans;
}
};
int main() {
Matrix A , ans;
long long T , n , k , sum;
//数据类型为long long
long long num[MAXN][MAXN];
//输入的数据存入数组
scanf("%lld" , &T);
while(T--){
scanf("%lld%lld\n", &n , &k);
memset(num , 0 , sizeof(num));
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++)
scanf("%lld" , &num[i][j]);
}
A.init(num);//初始化A矩阵
ans = quickpow(A , k);//求出矩阵的快速幂
}
}
分享到:
相关推荐
S7-200SMART_数据排序(整数+双整数+实数+无符号数)库文件及使用说明
S7-200SMART_计算算数平均值(整数+双整数+实数)库文件及使用说明
解大整数 矩阵 乘法 算法设计 实验报告与源代码工程
算法分析PPT(分治法-大整数、矩阵相乘).ppt)
这个代码是在探索者开发板的基础上写的,芯片型号stm32f407,可以同时显示整数和小数部分,下载到板子里就可以使用
快速幂算法在旋翼飞行器控制中的应用并非直接关联,快速幂作为一种高效的数学算法,主要用于计算大整数的幂次,尤其是在计算机科学和密码学中有广泛应用。不过,考虑到控制理论中的数学建模和优化计算也可能用到类似...
需要注意的是,快速幂算法不仅可以用于求解正整数的幂运算,还可以扩展到负整数、小数甚至矩阵的幂运算中。此外,在实际应用中,还需要注意处理底数为0或指数为0的特殊情况,以及考虑取模运算的需求,以满足不同的...
大整数的乘法 算法课程设计 比较简单大家快来看看吧
快速乘算法是一种用于高效计算两个大整数相乘的方法,它避免了传统的逐位相乘,而是通过分治策略将大整数分解为较小的部分进行计算,然后重新组合结果。这种方法可以显著减少计算所需的步骤,特别是在处理非常大的...
输入一个整数矩阵,计算位于矩阵边缘的元素之和。所谓矩阵边缘的元素,就是第一行和最后一行的元素以及第一列和最后一列的元素。 【输入】 第一行分别为矩阵的行数m和列数n(m,n),两者之间以一个空格分开。 接...
如题,内有PROTEUS仿真, 本来要做成浮点数的,但一开始选的键盘无小数点,最近又忙就没改
2019_2020学年八年级数学上册第十五章分式15.2分式的运算15.2.3整数指数幂负整数指数幂运算性质同步练习含解析新版新人教版20200406241
整数编码 遗传算法用于稀疏矩阵 基于matlab实现
很好的体现大数模板在各种应用中的不可思议的作用。
一个正整数用2的幂次方表示 实例一个正整数用2的幂次方表示 实例一个正整数用2的幂次方表示 实例一个正整数用2的幂次方表示 实例
运用简单的c语言实现整数幂问题,希望对相关人员有所帮助
现在有一个 m * n 的整数矩阵,请你编写一个程序计算出一条从左到右穿过矩阵的路径,并使此路径的费用最小。路径从矩阵的左侧的第一列的任意单元格开始,逐步穿过矩阵到达最右侧的一列的任意单元格。每一步是指从某...
大整数类型模板,各个接口已经封装完成,拿到就可以用,万分推荐!!! 大整数类型模板,各个接口已经封装完成,拿到就可以用,万分推荐!!! 大整数类型模板,各个接口已经封装完成,拿到就可以用,万分推荐!!!...
将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分: 6; 5+1; 4+2,4+1+1...
任意正整数都能拆成若干唯一的2的幂指数之和,php版本和js版本都有。