2014-02-17 16:38:11Morris
[UVA] 10547 - Hidden Truth in Recurrence
10547 - Hidd
Hidden Truth in Recurrence
Time Limit: 1 second
You are given a recursive function, which has the following form:
![](http://uva.onlinejudge.org/external/105/p10547a.gif)
Now, you have to find: | ![]() |
, where | ![]() |
![](http://uva.onlinejudge.org/external/105/p10547d.jpg)
Input
There will be less than 1001 lines of inputs in the input file. Each line will contain three integers: k (0<k<1019), n (0<n<1019) and t (0<t<10). Input will be terminated by three zeros for the value of k, n and t. You must not process this case.
Output
For each line of input, output the value of x. The output should be in the format shown in the sample output.
Sample Input | Sample Output |
1234 1234 4 2323 99999999999 8 4 99999 9 888 888 8 0 0 0 |
Case #1: 736 Case #2: 39087387 Case #3: 494777344 Case #4: 91255296 |
Problemsetter: Tanbir Ahmed, special thanks to Monirul Hasan
#include <stdio.h>
typedef unsigned long long ULL;
ULL modpow(ULL x, ULL y, ULL mod) {
ULL ret = 1;
x %= mod;
while(y) {
if(y&1)
ret = (ret * x)%mod;
y >>= 1, x = (x * x)%mod;
}
return ret;
}
int main() {
ULL k, n, t, a;
int cases = 0;
while(scanf("%llu %llu %llu", &k, &n, &t) == 3) {
if(k + n + t == 0)
break;
for(a = 1; t; t--, a *= 10);
printf("Case #%d: %llu\n", ++cases, modpow(k, n, a));
}
return 0;
}