题目描述

求 a 的 b 次方对 p 取模的值。

输入格式
三个整数 a,b,p ,在同一行用空格隔开。

输出格式
输出一个整数，表示a^b mod p的值。

数据范围
1≤a,b,p≤109
输入样例：
3 2 7
输出样例：
2

算法1

(暴力枚举) $O(m)$

暴力枚举也就是循环一遍即可

C++ 代码

#include <iostream>
using namespace std; 
#define ll long long //自定义ll为long long类型 
int main()
{
    ll a,b,c,ans=1;
    cin>>a>>b>>c;
    for (ll i=1;i<=b;i++)
        ans=ans*a%c;
    cout<<ans;
}

算法二

有BUG，主要是理解错误

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
#define ll long long
ll n,m,k;
ll power(ll n,ll m,ll k)
{
    ll ans=1;
    while(m)
    {
        if (m&1)
            ans=ans*n%k;//如果m为奇数，则需要乘以一遍n，m降次为偶数
        n=n*n%k; 
        ans=ans*n%k;//错误点，因为如果当前m为偶数的话，并不需要处理，只需要留到m为奇数时候处理
        m>>=1;
    }
    return (ans%k);
}
int main()
{
    cin>>n>>m>>k;
    cout<<power(n,m,k);
} 

正解

大致思路：我们知道，任何一个自然数都可以写成n=2^pi1+2^pi2+2^pi3+……2^pim,其中所有pi为非负整数，所以可以利用二分，将这一题次数m，转化一下即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring> 
using namespace std;
#define ll long long
ll n,m,k;
ll power(ll n,ll m,ll k)
{
    ll ans=1%k;
    while(m)
    {
        if (m&1)//如果m为奇数
            ans=ans*n%k;
        n=n*n%k;//将上一次的n进行平方
        m>>=1;
    }
    return (ans%k);
}
int main()
{
    cin>>n>>m>>k;
    n%=k;
    cout<<power(n,m,k);
}