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; }