算法训练 矩阵乘方
题目:
问题描述 给定一个矩阵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是一个2x2的矩阵,m不大于10000。 输入格式 输入第一行包含两个整数b, m,第二行和第三行每行两个整数,为矩阵A。 输出格式 输出两行,每行两个整数,表示A^b%m的值。 样例输入 2 2 1 1 0 1 样例输出 1 0 0 1
分析:
由题可得出一组等式:
当b = 0时,A^b%m=I%m;
当b = 奇数时,A^b%m=(A^(b/2)%m)^2%m
当b = 偶
数时,A^b%m=(A^(b-1)%m)^2%m
可得到递归式:
当b = 0时,f(0) = I%m;
当b = 奇数时,f(b) = f(b/2)^2%m
当b = 偶
数时,f(b) =
f(b-1)^2%m
代码在此:
#include<stdio.h>
#include<math.h>
#define SIZE 2
typedef struct matrix{
int map[SIZE][SIZE];
}Matrix;
Matrix I = {1,0,
0,1};
Matrix p;
int b,m;
Matrix mul_M(Matrix a,Matrix b){ //运算 (A乘A次,且都对m求余)
int i,j,k;
Matrix re;
for(i = 0;i < SIZE; i ++)
for(j = 0; j < SIZE;j ++){
re.map[i][j] = 0;
for(k = 0; k < SIZE; k ++)
re.map[i][j] += a.map[i][k]*b.map[k][j];
re.map[i][j] %= m;
}
return re;
}
Matrix fun () {
Matrix temp = p,re = I;
for(;;){
if(b <= 0)
break;
if(b&1 == 1){ //奇数
re = mul_M(re, temp);
b --;
}
temp = mul_M(temp, temp); //偶数
b = b>>1;
}
return re;
}
int main () {
int i,j;
scanf("%d%d", &b, &m);
scanf("%d%d", &p.map[0][0], &p.map[0][1]);
scanf("%d%d", &p.map[1][0], &p.map[1][1]);
Matrix re;
if(b == 0){ //处理b等于0的情况,可知b=0在fun()中不会运算
for(i = 0;i < SIZE; i ++)
for(j = 0; j < SIZE; j ++){
re.map[i][j] = I.map[i][j]%m;
}
} else {
re = fun();
}
for(i = 0; i < SIZE; i ++){
for(j = 0; j < SIZE; j ++)
printf("%d ",re.map[i][j]);
printf("\n");
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-27526.html