算法竞赛入门经典：第十章 数学概念与方法 10.5幂取模

/*
幂取模:
输入正整数a、n和m,输出a^n mod
m 的值,a, n , m <= 10^9
输入:
2 3 3
2 4 3
输出:
2
1
*/
/*
关键:
1 if(0 == n)//递归出口是n==1时，表示为1的数字,防止陷入n=0,n/2=0的无限递归之中
2 int x = powerMod(a,n/2,m);//这里采用递归，用n/2来缩小问题，起始是分治法，时间复杂度为O(log n)
3 long long ans = (long long)x * x % m;//这里ans由于涉及到long long，因此等式左边也需要用long long
4 return (int)ans;//最后由于除数<=10^9，因此最后的模只可能为int,因此需要将long long转换为int
*/
#include <stdio.h>
int powerMod(int a,int n,int m)
{
if(0 == n)//递归出口是n==1时，表示为1的数字,防止陷入n=0,n/2=0的无限递归之中
{
return 1;
}
int x = powerMod(a,n/2,m);//这里采用递归，用n/2来缩小问题，起始是分治法，时间复杂度为O(log n)
long long ans = (long long)x * x % m;//这里ans由于涉及到long long，因此等式左边也需要用long long
if(n % 2 == 1)
{
ans = ans * a % m;
}
return (int)ans;//最后由于除数<=10^9，因此最后的模只可能为int,因此需要将long long转换为int
}
void process()
{
int a,n,m;
while(EOF != scanf("%d %d %d",&a,&n,&m))
{
printf("%dn",powerMod(a,n,m));
}
}
int main(int argc,char* argv[])
{
process();
getchar();
return 0;
}

最后

以上就是孝顺小丸子为你收集整理的算法竞赛入门经典：第十章 数学概念与方法 10.5幂取模的全部内容，希望文章能够帮你解决算法竞赛入门经典：第十章 数学概念与方法 10.5幂取模所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。