快速幂与模运算

2019-05-15 约 309 字预计阅读 1 分钟

输入 b，p，k 的值，求 b^p mod k 的值。其中 b，p，k 为长整型数。

快速幂

假设p=22，那么p可以用16+4+2表示，即 $2^4+2^2+2^1$ 表示
上代码(没求模)：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
using ll = long long;

ll pow_mod(ll b, ll p)
{
    ll res = 1;
    while (p > 0)
    {
        if (p & 1)
        {
            res = (res * b);//当前位为1，则乘以b
        }
        b = (b * b);//求下一位的b
        p >>= 1;
    }
    return res ;
}

模运算

$$ (A+B) \mod b=(A \mod b+B \mod b) \mod b $$

$$ (A×B) \mod b =((A \mod b)×(B \mod b)) \mod b $$

所以上面那题的可以写出来了

 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 <stdio.h>

using ll = long long;

ll pow_mod(ll b, ll p, ll k)
{
    ll res = 1;
    while (p > 0)
    {
        if (p & 1)
        {
            res = (res * b) % k;
        }
        b = (b * b) % k;
        p >>= 1;
    }
    return res % k;
}

int main()
{
    ll b, p, k;
    scanf("%lld%lld%lld", &b, &p, &k);
    ll res = pow_mod(b, p, k);
    printf("%lld^%lld mod %lld=%lld", b, p, k, res);
    return 0;
}

目录

快速幂与模运算