Home 快速幂
Post
Cancel

快速幂

AcWing 90 64位整数乘法

Link

如果直接计算 a 乘 b 就会超过 long long 的最大范围, 所以采用快速幂的思想把 b 写成二进制形式, 如果第 i 位上为 1 就在结果上加 a*(1<<i), 并且每次加上之后取模就可以了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
typedef long long ll;
ll a,b,p,ans;
int main() {
    scanf("%lld%lld%lld",&a,&b,&p);
    while(b){
        if(b&1) ans=(ans+a)%p;
        b>>=1;
        a=(a<<1)%p;
    }
    printf("%lld\n",ans);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.