2012-01-12 17:21:08Morris
[UVA] 374 - Big Mod
Big Mod
| Big Mod |
Calculate
for large values of B, P, and M using an efficient algorithm. (That's right, this problem has a time dependency !!!.)
Input
Three integer values (in the order B, P, M) will be read one number per line. B and P are integers in the range 0 to 2147483647 inclusive. M is an integer in the range 1 to 46340 inclusive.
Output
The result of the computation. A single integer.
Sample Input
3 18132 17 17 1765 3 2374859 3029382 36123
Sample Output
13 2 13195
作法 : D&C
#include<stdio.h>
long long Mod(long long x, long long y, long long m) {
long long ans = 1, tmp = x;
while(y) {
if(y&1) {
ans *= tmp;
ans %= m;
}
y >>= 1;
tmp *= tmp, tmp %= m;
}
return ans;
}
int main() {
int B, P, M;
while(scanf("%d %d %d", &B, &P, &M) == 3) {
printf("%lld\n", Mod(B, P, M));
}
return 0;
}