思想
将指数表示成二进制的形式;
一个十进制的数它的数值必然 大于等于 它的二进制表达式的位数;
故可利用二分思想,将二进制数 依次右移并且判断最后一位数是否为1 (为1表示为奇数) ;
相比于线性时间O(n),该方法时间复杂度为O(log n), 远远快于 O(n);
代码如下
x
typedef long long ll;
const ll mod = 1e9 + 7;
xxxxxxxxxx
ll Counting(ll base, ll n) { //快速幂
ll power = 1; //幂也就是结果
while (n) {
if (n & 1) power *= base; //判断最后一位二进制数是否为1
base *= base;
n >>= 1; //去除最后一位二进制数
}
return power;
}
矩阵快速幂利用快速幂的思想,也就是二分思想把矩阵对半进行乘法;
xxxxxxxxxx
//矩阵快速幂
struct Matrix { //定义结构体矩阵
ll matrix[N][N];c
Matrix( ) { //构造函数初始化矩阵
memset(matrix, 0, sizeof(matrix)); //
}
};
xxxxxxxxxx
//矩阵乘法 Matrix multiplication
Matrix Matrix_multiplication(Matrix const &A, Matrix const &B) {
Matrix C;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
C.matrix[i][j] = (C.matrix[i][j] + A.matrix[i][k] * B.matrix[k][j]) % mod;
}
}
}
return C;
}
xxxxxxxxxx
//矩阵快速幂
Matrix Counting(Matrix const &base, ll n) { //快速幂
Matrix power, temp = base;; //幂
for (int i = 0; i < N; i++) {
power.matrix[i][i] = 1; //初始化为单位矩阵;
}
//与快速幂同理
while (n) {
if (n & 1) power = Matrix_multiplication(temp, power);
temp = Matrix_multiplication(temp, temp);
n >>= 1;
}
return power;
}
应用
xxxxxxxxxx
using namespace std;
//矩阵的阶数
typedef long long ll;
const int mod = 1e9 + 7; //数太大进行模
struct Matrix { //定义结构体矩阵
ll matrix[N][N];
Matrix( ) { //构造函数初始化矩阵
memset(matrix, 0, sizeof(matrix)); //
}
};
//矩阵乘法 Matrix multiplication
Matrix Matrix_multiplication(Matrix const &A, Matrix const &B) {
Matrix C;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
C.matrix[i][j] = (C.matrix[i][j] + A.matrix[i][k] * B.matrix[k][j]) % mod;
}
}
}
return C;
}
//矩阵快速幂
Matrix Counting(Matrix const &base, ll n) { //快速幂
Matrix power, temp = base;; //幂
for (int i = 0; i < N; i++) {
power.matrix[i][i] = 1; //初始化为单位矩阵;
}
//与快速幂同理
while (n) {
if (n & 1) power = Matrix_multiplication(temp, power);
temp = Matrix_multiplication(temp, temp);
n >>= 1;
}
return power;
}
//矩阵的输入
void Matrix_input(Matrix &A) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%lld", &A.matrix[i][j]);
}
}
}
//矩阵的输出
void Matrix_inout(Matrix const &A) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%lld ", A.matrix[i][j]);
}
cout << endl;
}
}
int main() {
ll n;
cin >> n; // 矩阵的指数
Matrix A, matrix_power, C;
Matrix_input(A); //输入矩阵A
cout << endl;
//C = A;
clock_t start1, end1;
//clock_t start2, end2;
start1 = clock();
matrix_power = Counting(A, n);
end1 = clock();
// start2 = clock();
// for (int i = 1; i < n; i++) {
// C = Matrix_multiplication(C, A);
// }
// en2 = clock();
Matrix_inout(matrix_power); //输出矩阵
cout << endl;
//Matrix_inout(C);
cout << "t1 = " << (double)(end1 - start1) / CLOCKS_PER_SEC << "s" << endl; //计算运行时间
//cout << "t2 = " << (double)(end2 - start2) / CLOCKS_PER_SEC << "s" << endl;
return 0;
}
xxxxxxxxxx
Fibonacci数列
f(n) = f(n - 1) + f(n - 2);
f(1) = f(2) = 1;
我发现 矩阵
xxxxxxxxxx
Matrix[2][2] = {
0, 1,
1, 1
};
有以下规律
矩阵Matrix 0次方为;
xxxxxxxxxx
cMatrix[2][2] = {
1, 0,
0, 1
};
f(1) = Matrix[1][1] = 1;
f(2) = Matrix[0][1] + Matrix[1][0] = 1;
矩阵Matrix 一次方为;
xxxxxxxxxx
Matrix[2][2] = {
0, 1,
1, 1
};
f(1) = Matrix[0][1] = Matrix[1][0] = 1;
f(2) = Matrix[1][1] = 1;
f(3) = Matrix[0][1] + Matrix[1][1] = 2;
矩阵Matrix 二次方为:
xxxxxxxxxx
Matrix[2][2] = {
1, 1,
1, 2
};
f(1) = Matrix[0][0] = 1;
f(2) = Matrix[0][1] = Matrix[1][0] = 1;
f(3) = Matrix[1][1] = 2;
f(4) = Matrix[0][1] + Matrix[1][1] = 3;
矩阵Matrix 三次方为:
xxxxxxxxxx
Matrix[2][2] = {
1, 2,
2, 3
};
f(2) = Matrix[0][0] = Matrix[0][0];
f(3) = Matrix[0][1] = Matrix[1][0] = 2;
f(4) = Matrix[1][1] = 3;
f(5) = Matrix[0][1] + Matrix[1][1] = 5;
矩阵Matrix 四次方为:
xxxxxxxxxx
Matrix[2][2] = {
2, 3,
3, 5
};
f(3) = Matrix[0][0] = 2;
f(4) = Matrix[0][1] = Matrix[1][0] = 3;
f(5) = Matrix[1][1] = 5;
f(6) = Matrix[0][1] + Matrix[1][1] = 8;
矩阵Matrix 五次方为:
xxxxxxxxxx
Matrix[2][2] = {
3, 5,
5, 8
};
f(4) = Matrix[0][0] = 3;
f(5) = Matrix[0][1] = Matrix[1][0] = 5;
f(6) = Matrix[1][1] = 8;
f(7) = Matrix[0][1] + Matrix[1][1] = 13;
矩阵Matrix 六次方为:
xxxxxxxxxx
Matrix[2][2] = {
5, 8,
8, 13
};
f(5) = Matrix[0][0] = 5;
f(6) = Matrix[0][1] = Matrix[1][0] = 8;
f(7) = Matrix[1][1] = 13;
f(8) = Matrix[0][1] + Matrix[1][1] = 21;
矩阵Matrix n次方为: 若 n >= 2;
xxxxxxxxxx
Matrix[2][2] = {
f(n - 1), f(n),
f(n), f(n + 1)
};
f(n - 1) = Matrix[0][0];
f(n) = Matrix[0][1] = Matrix[1][0];
f(n + 1) = Matrix[1][1] = 13;
f(n + 2) = Matrix[0][1] + Matrix[1][1];
矩阵Matrix n次方为: 若 n >= 1, 且f(0) = 0; 则有
xxxxxxxxxx
Matrix[2][2] = {
f(n - 1), f(n),
f(n), f(n + 1)
};
f(n - 1) = Matrix[0][0];
f(n) = Matrix[0][1] = Matrix[1][0];
f(n + 1) = Matrix[1][1] = 13;
f(n + 2) = Matrix[0][1] + Matrix[1][1];
故代码如下:
xxxxxxxxxx
using namespace std;
//矩阵的阶数
typedef long long ll;
const int mod = 1e9 + 7; //数太大进行模
struct Matrix { //定义结构体矩阵
ll matrix[N][N];
Matrix( ) { //构造函数初始化矩阵
memset(matrix, 0, sizeof(matrix)); //
}
};
//矩阵乘法 Matrix multiplication
Matrix Matrix_multiplication(Matrix const &A, Matrix const &B) {
Matrix C;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
C.matrix[i][j] = (C.matrix[i][j] + A.matrix[i][k] * B.matrix[k][j]) % mod;
}
}
}
return C;
}
//矩阵快速幂
Matrix Counting(Matrix const &base, ll n) { //快速幂
Matrix power, temp = base;; //幂
for (int i = 0; i < N; i++) {
power.matrix[i][i] = 1; //初始化为单位矩阵
}
//与快速幂同理
while (n) {
if (n & 1) power = Matrix_multiplication(temp, power);
temp = Matrix_multiplication(temp, temp);
n >>= 1;
}
return power;
}
int main() {
/*
ll matrix_temp[2][2] = {
0, 1,
1, 1
};
*/
Matrix matrix_temp;
matrix_temp.matrix[0][0] = 0;
matrix_temp.matrix[0][1] = 1;
matrix_temp.matrix[1][0] = 1;
matrix_temp.matrix[1][1] = 1;
// ll matrix_fibonacci[1][2] = {
// 1,//f(1) = 1; == f(n - 1);
// 1 //f(2) = 1; == f(n);
// };
ll n;// 矩阵的指数
while (cin >> n) {
cout << endl;
Matrix matrix_power;
matrix_power = Counting(matrix_temp, n);
printf("f(%lld) = %lld\n", n - 1, (ll)(matrix_power.matrix[0][0] % mod));
printf("f(%lld) = %lld\n", n, (ll)(matrix_power.matrix[0][1] % mod));
// printf("f(%lld) = %lld\n", n, (ll)(matrix_power.matrix[1][0] % mod));
printf("f(%lld) = %lld\n", n + 1, (ll)(matrix_power.matrix[1][1] % mod));
printf("f(%lld) = %lld\n", n + 2, (ll)((matrix_power.matrix[1][1] + matrix_power.matrix[0][1]) % mod));
cout << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << matrix_power.matrix[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
return 0;
练习 http://acm.hdu.edu.cn/showproblem.php?pid=2817 hdu 2817
xxxxxxxxxx
// AC代码
using namespace std;
typedef long long ll;
ll Counting(ll base, ll n) { //快速幂
ll power = 1; //幂也就是结果
while (n) {
if (n & 1) power = (power * base) % 200907; //判断最后一位二进制数是否为1
base = (base * base) % 200907;
n >>= 1; //去除最后一位二进制数
}
return power % 200907;
}
int main() {
int n;
ll a, b, c, k;
cin >> n;
while (n--) {
scanf("%lld %lld %lld %lld", &a, &b, &c, &k);
if(c + a == 2 * b) {
ll d = (b - a) % 200907;
ll t = ((a % 200907) + ((k - 1) % 200907) * d) % 200907;
cout << t << endl;
} else {
ll q = b / a;
cout << a * Counting(q, k - 1) % 200907 << endl;
}
}
return 0;
}
http://acm.hdu.edu.cn/showproblem.php?pid=1061 hdu 1061
xxxxxxxxxx
//AC代码
using namespace std;
typedef long long ll;
const ll mod = 10;
ll Counting(ll base, ll n) {
ll power = 1;
while (n) {
if (n & 1) power = power * base % mod;
base = base * base % mod;
n >>= 1;
}
return power;
}
int main() {
int t;
cin >> t;
ll n;
while (t--) {
scanf("%lld", &n);
int temp = Counting(n, n) % 10;
printf("%d\n", temp);
}
return 0;
}
http://acm.hdu.edu.cn/showproblem.php?pid=5392 hdu5392 目前不会,置换群幂运算,表示不懂。
原理
xxxxxxxxxx
利用辗转相除法
代码实现如下
xxxxxxxxxx
typedef long long ll;
//法一 迭代法
ll gcd(ll a, ll b) { //默认a > b;
while (b) {
ll temp = a;
a = b;
b = temp % b;
}
return a;
}
// 法二 递归法
ll gcd_1(ll a, ll b) { //默认a > b;
return b ? gcd_1(b, a % b) : a;
}
验证
xxxxxxxxxx
using namespace std;
typedef long long ll;
//法一 迭代法
ll gcd(ll a, ll b) { //默认a > b;
while (b) {
ll temp = a;
a = b;
b = temp % b;
}
return a;
}
// 法二 递归法
ll gcd_1(ll a, ll b) { //默认a > b;
return b ? gcd_1(b, a % b) : a;
}
int main() {
ll a, b;
while (cin >> a >> b) {
cout << __gcd(a, b) << endl; // C++内置函数 头文件 <algorithm>
cout << gcd(a, b) << endl; // d迭代
cout << gcd_1(a, b) << endl; //递归
}
return 0;
}
实现了GCD, LCM不就简单了么.
原理:
xxxxxxxxxx
最小公倍数为 a * b / gcd(a, b)
xxxxxxxxxx
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b; // 防止 a * b 溢出;
}
快速线性筛法没有冗余,不会重复筛除一个数,所以几乎是线性的。 虽然从代码上分析,时间复杂度并不是O(n),而是接近线性而已。
xxxxxxxxxx
void init(int n) {
for (int i = 2; i <= n; i++) {
if (!prime[i]) prime[++prime[0]] = i; //prime[0]存储素数个数,顺便把素数按顺序存储;
for (int j = 1; j <= prime[0]; j++) {
if ( i * prime[j] > n) break;
prime[i * prime[j]] = 1; //标记合数
if (!(i % prime[j])) break; // 减少重复标记
}
}
}