LiveArchive-4104, UVa-1230 : MODEX

問題概要

x,y,z(いずれも値はsigned intに収まる)が与えられるのでx^y (z)を求める問題。

解法

いわゆるバイナリ法を使って計算する。

acceptされたコード

計算量O(log Y)。

#include <cstdio>
using namespace std;

typedef long long int64;
int MOD, X, Y;

int64 pow_bin(int64 x, int n){
	if(x == 0){
		return 0;
	}
	int64 ret = 1;
	for(;n;n>>=1){
		if( n&1 ){
			ret = ret * x % MOD;
		}
		x = x * x % MOD;
	}

	return ret;
}

void init(){
	scanf("%d%d%d", &X, &Y, &MOD);
}

int solve(){
	return pow_bin(X, Y);
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		init();
		printf("%d\n", solve());
	}

	return 0;
}