3012.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 43 行

Source

Problem Id:3012  User Id:fzk 
Memory:44K  Time:781MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>

int main( ) {
	int n, k, m, t, i;
	__int64 a[32], ans, temp;
	
	scanf( "%d", &t );

	while( t-- ) {
		scanf( "%d%d%d", &n, &k, &m );

		a[0] = 10%m;
		ans = 1;
		temp = 1;
		for( i=1; i<32; i++ )
			a[i] = (a[i-1]*a[i-1])%m;
		
		for( i=0; (1<<i)<=k; i++ )
			if( k & (1<<i) )
				temp = (temp*a[i])%m;
		
		a[0] = (temp+1)%m;
		for( i=1; i<32; i++ )
			a[i] = (a[i-1]*a[i-1])%m;

		for( i=0; (1<<i)<=n; i++ )
			if( n & (1<<i) )
				ans = (ans*a[i])%m;

		printf( "%d\n", ans );
	}
	return 0;
}