89. a^b

题目描述

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

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

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

数据范围
0≤a,b,p≤109
数据保证 p≠0

输入样例

3 2 7

输出样例

2

算法1

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

TLE代码

#include<bits/stdc++.h>
using namespace std;
int a,b,c,ans=1;
int main()
{
    scanf("%d%d%d",&a,&b,&c);
    ans=1%c;//b=0时不会进循环 
    for(int i=1;i<=b;i++)
        ans=ans*a%c;
    printf("%d",ans);
    return 0;
}

算法2

时间复杂度O(log b)

AC代码,快速幂

#include<bits/stdc++.h>
using namespace std;
int a,b,p;
int main()
{
    scanf("%d%d%d",&a,&b,&p);
    int ans=1%p;
    while(b)
    {
        if(b&1) ans=a*1ll*ans%p;//a*ans可能超出int范围，所以要强制转换成long long
        a=a*1ll*a%p;//不能缩写成a*=a*1ll%p,这是mod完再乘;*1ll是乘以long long类型的1
        b=b>>1;
    }
    printf("%d",ans);
    return 0;
}