AcWing 89. \(a\)^\(b\)

题目描述

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

输入格式

三个整数 \(a,b,p\) ,在同一行用空格隔开。

输出格式

输出一个整数，表示\(a^b \mod p\)的值。

数据范围

\(1\le a,b,p\le 10^9\)

输入样例：

3 2 7

输出样例：

2

---

提交地址

【Luogu】T155278

如果显示您无权查看该题目，则请加入团队

题解

算法1

(暴力枚举) \(\mathrm O(m)\)
暴力枚举也就是循环一遍即可

C++ 代码

/**
**********************************************************************************************************************************************************************************************************************************
* @file:	AC91.bf.cpp
* @author:	秦淮岸灯火阑珊
* @date:	2020年11月08日 18:12:03 星期天
* @brief:	CH0101 Acwing 91
* @Error:	WA on data 123456789 0 1, get 1, expected 0
**********************************************************************************************************************************************************************************************************************************
**/
#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;
}

正解

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

/**
**********************************************************************************************************************************************************************************************************************************
* @file:	AC91.bf.cpp
* @author:	lyd
* @date:	2020年11月08日 18:12:03 星期天
* @brief:	CH0101 Acwing 91
**********************************************************************************************************************************************************************************************************************************
**/
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a, b, p;

int power(int a, int b, int p)
{ // calculate (a ^ b) mod p
	int ans = 1 % p;
	for (; b; b >>= 1)
	{
		if (b & 1)
			ans = (long long)ans * a % p;
		a = (long long)a * a % p;
	}
	return ans;
}

int main()
{
	cin >> a >> b >> p;
	cout << power(a, b, p) << endl;
}