You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

1.0 KiB

题目传送门

一、题目描述

ab 次方对 p 取模的值。

二、解题方法

一看到这道题,就可以知道是快速幂。 这道题的重点是快速幂,那我就来认真讲讲。

快速幂是使用二进制的思想来在 O(logn) 的时间内解决幂的问题的方法。

举个栗子 710次方

计算思路: 10 = (1010)_2

从右向左 7^1=7 7^2 = 7^1 * 7^1 7^4 = 7^2 * 7^2 7^8 = 7^4 * 7^4

如上面的办法,我们只需要计算4次,成倍的翻番,而不用最笨的乘10次!所得的结果相乘或不断取模就行了。

三、实现代码

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

int main() {
    LL a, b, p, res = 1;
    cin >> a >> b >> p;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    printf("%lld\n", res % p);
    return 0;
}