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

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

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

• 题目描述
• 输入格式
• 输出格式
• 输入输出样例
• 说明/提示
• C++代码

---

题目描述

给你三个整数 b,p,k，求 (b^p mod 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 mod 9 = 7)。

数据规模与约定

• 对于 100% 的数据，保证 (0le 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;
}