首先介绍快速幂:
快速幂可以在常数时间内计算$$a^b$$,而朴素的算法则需要$$O(b)$$
思想:将b转换为二进制,则
$$b=1+2+4+8+……$$
$$a^b=a^{1}*a^{2}*a^{4}*….=a^{1}*(a^{1})^{2}*((a^{1})^{2})^{2}*…$$
例如:
求$$3^5$$
$$\because 5=1+4$$
$$\therefore 3^5=3^{1+4}=3^1*3^4$$
先计算$$3^1=3$$,结果乘上3 然后计算$$(3^1)^2=3^2=9$$,然后计算$$(3^2)^2=3^4=81$$,结果乘上81,最终结果为$$3*81=243$$
代码:
#include
#include
#include
#include
#include
#include
#include
using namespace std;
using int_t = long long int;
int_t fastPower(int_t base, int_t index) {
//结果
int_t result = 1;
//只要指数不为0就一直循环
while (index) {
//index的最低位为1,结果中应该乘上base的对应次幂
if (index & 1) {
result = result*base;
}
base = base*base;
//index右移一位
index >>= 1;
}
return result;
}
int main() {
int_t base, index;
while (true) {
cin >> base>>index;
if (base == 0 && index == 0) break;
cout << fastPower(base, index) << endl;
}
return 0;
}
矩阵快速幂:
使用快速幂的思想来计算矩阵的幂
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
using int_t = unsigned long long int;
const int_t mod = (int_t) 1e9 + 7;
//Matrix的前置声明,用于下面两个函数
template
class Matrix;
//友元函数的声明
//模板类的友元函数必须显式的写明模板
template
ostream& operator<<(ostream & os, const Matrix & mat);
template
istream& operator>>(istream & os, const Matrix & mat);
template
class Matrix {
private:
ValType* data;
int_t row;
int_t col;
int_t size;
int_t num;
public:
//析构函数,释放内存
~Matrix() {
delete[] data;
}
//拷贝构造函数
Matrix(const Matrix& other) :
row(other.row), col(other.col), size(other.size), num(other.num) {
data = new ValType[other.num];
memcpy(data, other.data, other.size);
}
//默认构造函数,动态分配内存
Matrix(int_t r, int_t c) :
row(r), col(c) {
this->row = r;
this->col = c;
num = (row + 1)*(col + 1);
data = new ValType[num];
size = sizeof (ValType) * num;
memset(data, 0, size);
}
//访问矩阵的某个元素
ValType& at(int_t r, int_t c) {
return data[c + r * col];
}
//重载的*运算符,矩阵无法相乘时会抛出异常
Matrix operator*(Matrix& mat) throw (const char*) {
if (this->col != mat.row) throw "Column number of matrix1 doesn't equals that in matrix2";
Matrix result(this->row, mat.col);
for (int_t i = 1; i <= this->row; i++) {
for (int_t j = 1; j <= mat.col; j++) {
int_t sum = 0;
for (int_t x = 1; x <= this->col; x++) {
sum = (sum % mod + at(i, x) % mod * mat.at(x, j) % mod) % mod;
}
result.at(i, j) += sum % mod;
}
}
return result;
}
int_t getCol() const {
return col;
}
int_t getRow() const {
return row;
}
//赋值构造函数
Matrix & operator=(const Matrix & other) {
this->col = other.col;
this->num = other.num;
this->row = other.row;
this->size = other.size;
this->data = new ValType[num];
memcpy(data, other.data, size);
}
//友元,函数名后必须写<>以告诉编译器这个友元使用了模板,如果不能从参数中推断模板类型那么还必须在<>内写上模板类型
friend ostream& operator<< <>(ostream & os, const Matrix & mat);
friend istream& operator>> <>(istream & os, const Matrix & mat);
};
//友元函数的实现
template
ostream & operator<<(ostream & os, Matrix & mat) {
for (int_t i = 1; i <= mat.getRow(); i++) {
for (int_t j = 1; j <= mat.getCol(); j++) {
os << mat.at(i, j) % mod << " ";
}
os << endl;
}
return os;
}
template
istream & operator>>(istream & is, Matrix & mat) {
for (int_t i = 1; i <= mat.getRow(); i++) {
for (int_t j = 1; j <= mat.getCol(); j++) {
is >> mat.at(i, j);
mat.at(i, j) %= mod;
}
}
return is;
}
using MatType = Matrix;
int main() {
int_t n, index;
cin >> n>>index;
MatType mat(n, n);
cin>>mat;
MatType result = mat;
//普通的快速幂
for (index--; index; index>>=1,mat = mat * mat) {
if (index & 1) result = result * mat;
}
cout << result;
return 0;
}
此外,矩阵$$A=\begin{bmatrix}
0&1 \\
1&1
\end{bmatrix}$$的n次方所得的矩阵的对角线上的元素即为斐波那契数列的第n项。