快速幂

Tepley · 2025-01-19 19:02:12 · 算法·理论

1.计算幂

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

#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}

所以代码就出来了

#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;
}