A^B Mod C （快速幂）

Lokinli

发布于 2023-03-09 16:04:02

2610

发布于 2023-03-09 16:04:02

文章被收录于专栏：以终为始

题目描述：给出3个正整数A B C，求A^B Mod C。

例如，3 5 8，3^5 Mod 8 = 3。

Input3个正整数A B C，中间用空格分隔。(1 <= A,B,C <= 10^9)Output输出计算结果Sample Input

3 5 8

Sample Output

代码实现：

#include<bits/stdc++.h>

using namespace std;

long long int pow_mod(long long int a, long long int k, long long int c)
{
    long long int ans = 1;
    while(k)
    {
        if(k % 2) ans *= a;
        a = (a * a) % c;
        k /= 2;
        ans %= c;
    }
    return ans;
}

int main()
{
    long long int a, b, c;
    scanf("%lld %lld %lld", &a, &b, &c);
    a %= c;
    printf("%lld\n",pow_mod(a,b,c));
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-03-18，如有侵权请联系 cloudcommunity@tencent.com 删除

input