快速幂

1.计算幂

通常的方法是写一个函数或调用　 $pow()$ 　函数

CPP

#include <bits/stdc++.h>
using namespace std;

void faction(int n, int power) {
	int ans = 1;
	for (int i = 1; i <= power; i ++) ans *= n;
	printf("%d", ans);
}

int main() {
	int A, B scanf("%d %d", &A, &B);
	faction(A, B); //pow(A, B);
	return 0;
}

但是这种方法的时间复杂度是　

O(B)

　，随着　b　的增大，它的复杂度会呈指数增加(即指数函数也称爆炸函数)。

if 　(B　 == 　10 ^ 8)

　就要循环　

10^8

　次，成本太高。同时，　

pow()

　的精度不够，所以不怎用。

2.快速幂引入

它是一种常见的方法，它可以将指数进行折半处理，因此它的时间复杂度为　

O(logN)

3.快速幂

核心：利用二进制进行快速运算例如　

a^b

　中　

b = 15(10)

,　10　进制的　15　转为二进制为　1111(2). 即　

15 = 1 * 2 ^ 0 + 1 * 2 ^ 1 + 1 * 2 ^ 2 + 1 * 2 ^ 3

运用初中数学知识得到：　

a ^ {15} = a^ {1111} = a ^ {2 ^ 3 * 1} * a ^ {2 ^ 2 * 1} * a ^ {2 ^ 1 * 1} * a ^ {2 ^ 0 * 1}

∵

a ^ 0 = 1(a ≠ 0)

∴

a^{15} 　只与　a ^ {2 ^ 3 * 1}, a ^ {2 ^ 2 * 1}, a ^ {2 ^ 1 * 1}

　这三项有关

有发现它正好是　1110(2)　非零位的项，只需要将它们累加起来就好。最后发现了这个式子：

a ^ 1 * 1 = a ^ {2 ^ 3} * a ^ {2 ^ 2} * a ^ {2 ^ 1}

所以代码就出来了

CPP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll faction(int a, int b)
{
    ll ans = 1;   
    while (b > 0)          
    {
        if (b & 1) ans *= a;    
        a *= a;           
        b >>= 1; 
    }
    printf("%lld", ans);
}


int main() {
	ll a, b; scanf("%lld %lld", &a, &b);
	faction(a, b);
	return 0;
}

文章操作

1.计算幂

2.快速幂引入

3.快速幂

相关推荐

评论

快速幂