当前位置：首页 > article >正文

AcWing89. a^b

article 2024/11/13 13:07:34

题目

求 $a$ 的 $b$ 次方对 $p$ 取模的值。

输入格式

三个整数 $a, b, p,$ 在同一行用空格隔开。

输出格式

输出一个整数，表示 a^b mod p 的值。

数据范围

$0≤a,b≤10^9$

$1≤p≤10^9$

输入样例

3 2 7

输出样例

思路

快速幂。

任何一个整数都可以唯一表示为若干指数不重复的 2 的次幂的和。即是说如果 $b$ 在二进制表示下 $k$ 位，其中第 $\le i \le k)$ 位的数字是 $c_i$ ，那么：
$b = c_{k-1}2^{k-1} + c_{k-2}2^{k-2} + ... + c_0 2^0$
于是
$^b = a^{c_{k-1}\times2^{k-1}} * a^{c_{k-2} \times 2^{k-2}} * ... * a^{c_0 \times 2^0}$
因为 $\lceil log_2(b+1) \rceil$ ，所以上式乘积项的数量不多于 $\lceil log_2(b+1) \rceil$ 个。又因为：
$a^{2^i} = (a^{2^{i-1}})^2$
所以可以通过 $k$ 次递归求出每个乘积项，当 $c_i = 1$ 时，将该乘积项累积到答案中。 $KaTeX parse error: Expected 'EOF', got '&' at position 3: b &̲ 1$ 运算可以取出 $b$ 在二进制表示下的最低位，而 $b >> 1$ 运算可以舍去最低位，在递推过程中将二者集合，就可以遍历 $b$ 在二进制表示下的所有数位 $c_i$ 。

整个算法的时间复杂度为 $O(log_2b)$ 。

代码

#include <cstdio>

using namespace std;

int main() {
    int a, b, p;
    scanf("%d%d%d", &a, &b, &p);
    
    int ans = 1 % p;
    
    while (b) {
        if (b & 1) ans = (long long)ans * a % p;
        b >>= 1;
        a = (long long)a * a % p;
    }
    
    printf("%d\n", ans);
    
    return 0;
}

注意

在 C++ 语言中，两个数值执行算术运算时，以参与运算的最高数值类型为基准，与保存结果的变量类型无关。换言之，虽然两个 32 位整数的乘积可能超过 int 类型的表示范围，但是 CPU 只会用 1 个 32 位寄存器保存结果，造成越界现象。因此，必须把其中一个数强制转换成 64 位整数类型 long long 参与运算，从而得到正确的结果。最终对 $p$ 取模以后，执行赋值操作时，该结果会被隐式转换成 int 存回 ans 中。

查看全文

http://www.kler.cn/a/108852.html