UVa 374 Big Mod

已知 (A^n)%M=(A%M)*(A%M)*(A%M)*......*(A%M)%M

可用遞迴 (A^n)%M = (A^(n/2))%M * (A^(n/2))%M %M

	#include<cstdio>
	using namespace std;
	typedef long long int llt;
	llt mod(llt B,llt P,llt M);
	int main()
	{
	llt B,P,M;
	while(scanf("%lld %lld %lld",&B,&P,&M)!=EOF){
	printf("%lld\n",mod(B,P,M));
	}
	return 0;
	}
	llt mod(llt B,llt P,llt M)
	{ //遞迴 (A^n)%M = (A^(n/2))%M * (A^(n/2))%M %M
	if(P==0) return 1;
	if(P==1) return B%M;
	llt temp = mod(B,P/2,M); //temp=(A^(n/2))%M
	if(P%2==1) return temp*temp*B%M; //P為奇數
	else return temp*temp%M;
	}

view raw UVa 374 Big Mod.cpp hosted with ❤ by GitHub