洛谷题单指南-分治与倍增-P1226 【模板】快速幂

原题链接：https://www.luogu.com.cn/problem/P1226

题意解读：快速幂模版题。

解题思路：

1、分治法

要计算a^b，可以对b分情况讨论：

如果b是偶数，即b = 2t，a^b = a^t * a^t

如果b是奇数，即b = 2t + 1，a^b = a * a^t * a^t

很容易用递归实现

100分代码：

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

int a, b, p;

//计算x^y%p
int ksm(int x, int y)
{
    if(y == 0) return 1 % p;
    int t = ksm(x, y / 2);
    if(y % 2 == 0) return 1ll * t * t % p;
    else return 1ll * x * t % p * 1ll * t % p;
}

int main()
{
    cin >> a >> b >> p;
    printf("%d^%d mod %d=%d", a, b, p, ksm(a, b));
}

2、倍增法

基于任意整数都可以转换成若干个2的次幂之和，如15 = 2^0 + 2^1 + 2^2 + 2^4

这样一来，计算a^b，如果b=15，可以变成计算a^(2^0 + 2^1 + 2^2 + 2^4)

由于15用二进制表示为1111，因此可以通过移位操作来枚举15的每一个2的次幂，累乘即可

每移位一次，要累加的值a = a * a，如果当前位是1，说明需要累乘，如果当前位为0，说明不需要累乘

100分代码：

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

int a, b, p;

//计算x^y%p
int ksm(int x, int y)
{
    int res = 1;
    while(y)
    {
        if(y & 1) res = 1ll * res * x % p;
        y = y >> 1;
        x = 1ll * x * x % p;
    }
    return res;
}

int main()
{
    cin >> a >> b >> p;
    printf("%d^%d mod %d=%d", a, b, p, ksm(a, b));
}