A 的 B 次方

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 481 字

求a^bmodm的值

一本通
练习

正文

/*
原题：A 的 B 次方
题意：求 a^b mod m 的值。
思路：用快速幂计算 a^b mod m，乘法用 long long 防止 1e9 量级相乘溢出。
复杂度：O(log b) 时间 / O(1) 空间
易错点：a、b、m 可达 1e9，乘积用 long long；先对底数取模。
*/
#include <bits/stdc++.h>
using namespace std;
long long qpow(long long a,long long b,long long m){
    long long res=1%m;
    a%=m;
    while(b){
        if(b&1){ res=res*a%m; }
        a=a*a%m;
        b>>=1;
    }
    return res;
}
int main(){
    long long a,b,m;
    cin>>a>>b>>m;
    cout<<qpow(a,b,m)<<'\n';
    return 0;
}

A 的 B 次方

正文

一本通·提高篇的其它内容