[UVa]374:Big Mod

首先，
要先知道數學式子：(A*B)%C = (A%C) * (B%C)。
因此我就可以不用把B^P算完再去對M取餘數，
但是如果是((((B%M)*B)%M)*B)%M.....的話，
會TLE的，
所以算次方請用次方除二相乘的遞迴來算次方，
也就是 (B^P)%M = (B^(P/2)%M) * (B^(P/2)%M) 這樣遞迴。

[C](0.012)

	#include<stdio.h>
	long long modpow( long long B, long long P, long long M )
	{
	if( P == 0 )
	return 1;
	else if( P == 1 )
	return B%M;
	else
	{
	long long result = modpow( B, P/2, M );
	if( P % 2 )
	return result * result * B % M;
	else
	return result * result % M;
	}
	}
	int main()
	{
	long long B, P, M;
	while( scanf( "%lld%lld%lld", &B, &P, &M ) != EOF )
	{
	long long i = 0;
	long long R = modpow( B, P, M );
	printf( "%lld\n", R );
	}
	return 0;
	}

view raw UVa374.c hosted with ❤ by GitHub