P1226. 模板题_快速幂

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 146 阅读时长 ≈ 1 分钟

考点

  • 快速幂

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll binpow(ll a, ll b, ll p)
{
    a %= p;
    ll ans = 1;
    while (b > 0)
    {
        if (b & 1)
            ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

int main()
{
    ll a, b, p;
    cin >> a >> b >> p;
    printf("%lld^%lld mod %lld=%lld", a, b, p, binpow(a, b, p));
    return 0;
}

思路

标准的快速幂模板题，快速幂的具体原理可以参照Wiki

答案要求我们对结果取模；由于取模操作不会对乘法运算造成影响，所以在求幂次的过程中取模操作可以并行