算法题每日一练—第61天：数的幂次

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、前言

给定三个正整数 N、M、P，求解$N^MmodP$的具体值。

第 1 行为一个整数 T，表示测试数据数量。

接下来的 T 行每行包含三个正整数 N、M、P，$1≤T≤10^5，1≤N,M,P≤10^9$。

输出$N^MmodP$的结果。

题目链接：数的幂次。

二、题目要求

样例

输入：
3 
2 3 7 
4 5 6 
5 2 9
输出：
1 
4 
7
复制代码

考察

1.位运算中等题型、快速幂
2.建议用时15~30min
复制代码

三、问题分析

本题是位运算的第16题，没了解过位运算相关知识点可以看这一篇文章，讲解比较详细：

算法题每日一练—第45天：位运算。

如果你了解过位运算相关知识点，但没有了解过快速幂，可以先看这一篇

算法题每日一练—第60天：快速幂

知识点介绍，然后再回来做这一题会发现非常简单。

这一题的数据量比较大，如果用普通的次方相乘取模运算肯定会超时的，而用快速幂最多也只需要计算32位就可以完成计算，为了保险起见我们用64的long long 存储。

四、编码实现

#include<iostream>
#include<math.h>
using namespace std;
typedef long long ll;//定义long long
ll quick_pow(ll n,ll m,ll p)//快速幂模板
{
	ll ans=1,base=n;
	while(m!=0)
	{
		if(m&1)
			ans=(ans*base)%p;
		base=(base*base)%p;
		m=m>>1;
	}
	return ans;
}
int main()
{
	ll t,n,m,p,i;//初始化数据
	cin>>t;
	for(i=0;i<t;i++)//循环判断
	{
		cin>>n>>m>>p;
		cout<<quick_pow(n,m,p)<<"\n";//输出结果
	}
	return 0;
}
复制代码

五、测试结果