OJ Board

I have got many WAs.
As I understood the program should calculate (k^n) mod (10^t)
Am I right ? If I am then it is very very strange.
To calculate (k^n) mod (10^t) I use Modular-Exponentiation Algo based on repeated squaring. But WA

Here is my program
[cpp]#include <iostream.h>
#include <stdio.h>

int main()
{
long long n, k, t, m, testid = 0, d;
while (1)
{
scanf("%lld %lld %lld", &k, &n, &t);
if (n + k + t <= 0) break;
cout << "Case #" << ++testid << ": ";
m = 1;
while (t--) m *= 10;
int b[100], bcnt = 0;
while (n)
{
b[bcnt++] = n % 2;
n /= 2;
}
d = 1;
for (n = bcnt - 1; n >= 0; n--)
{
d = (d * d) % m;
if (b[n]) d = (d * k) % m;
}
printf("%lld\n", d);
}
return 0;
}[/cpp]

Hrmmm... weird, I did this recursively, so I'll check your program..

Change it to:
Or something. Your attempt to try to be slick made n + k overflows long long, and thus prematurely terminates.

here's my input: Actually, I used unsigned long long, so maybe that's it..

Thanks for advise - I change my code, but now I get Runtime Error
Can you say why it's happen ?

[cpp]#include <iostream.h>
#include <stdio.h>

int main()
{
unsigned long long n, k, t, m, testid = 0, d;
while (1)
{
scanf("%lld %lld %lld", &k, &n, &t);
if (n == 0 && k == 0 && t == 0) break;
cout << "Case #" << ++testid << ": ";
m = 1;
while (t--) m *= 10;
int b[100], bcnt = 0;
while (n)
{
b[bcnt++] = n % 2;
n /= 2;
}
d = 1;
for (n = bcnt - 1; n >= 0; n--)
{
d = (d * d) % m;
if (b[n]) d = (d * k) % m;
}
printf("%lld\n", d);
}
return 0;
}[/cpp]

Revenger:
You should try to use %llu instead of %lld to read/write an unsigned long long variable.

if (b[n]) d = (d * k) % m;

change it to d= (d * (k%m)) % m, since d * k may exceed 64 bit range.

Thanks, I get AC

Could someone please help me how to solve the recurrence?
how can that recurrence only be k^n mod 10^t?
thanx

regards,
stephanus