洛谷-P1226 【模板】快速幂||取余运算

洛谷-P1226 【模板】快速幂||取余运算

原题链接:https://www.luogu.com.cn/problem/P1226


题目描述

给你三个整数 b,p,k,求 \(b^p \bmod k\)。

输入格式

输入只有一行三个整数,分别代表 b,p,k

输出格式

输出一行一个字符串 b^p mod k=s,其中 b,p,k 分别为题目给定的值, s 为运算结果。

输入输出样例

输入 #1

2 10 9

输出 #1

2^10 mod 9=7

说明/提示

样例输入输出 1 解释

\(2^{10} = 1024\),\(1024 \bmod 9 = 7\)。

数据规模与约定

  • 对于 100% 的数据,保证 \(0\le b,p < 2^{31}\),\(1 \leq k \leq 2^{31}\)。

C++代码

#include <iostream>
using namespace std;
#define ll long long

ll mypow(ll b, ll p, ll k) {
    if(p==1)
        return b%k;
    else if(p==0)
        return 1%k;
    ll ans;
    b%=k;
    if(p%2==0) {
        ans=mypow(b,p/2,k)%k;
        return ans*ans%k;
    }else{
        ans=mypow(b,(p-1)/2,k)%k;
        return ans*ans*b%k;
    }
}

int main() {
    ll b,p,k,ans;
    cin>>b>>p>>k;
    ans=mypow(b,p,k);
    cout<<b<<'^'<<p<<" mod "<<k<<'='<<ans<<endl;
    return 0;
}
上一篇:LeetCode题解(python)-50. Pow(x, n)


下一篇:PTA《C语言程序设计实验与习题指导(第3版)》题目集 实验2-4-5 简单实现x的n次方 (10 分)