a^k mod n.cpp

来自「数值分析中常用的几种算法的实现」· C++ 代码 · 共 25 行

#include<stdio.h>
//log2k;
int compute(int a,int k,int n){
	int t,p,q;
	if(k==0)
		return 1;
	p=k%2;
	t=compute(a,k/2,n);
	if(p==0){
		q=1;
	}
	else
		q=a;
	return (t*t*q)%n;
}
int main(){
	int a,k,n,t;
	scanf("%d%d%d",&a,&k,&n);
	if(n==1){
		printf("0\n");
		return 0;
	}
	t=compute(a,k,n);
	printf("%d\n",t);
}