10547 - Hidden Truth in Recurrence

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

10547 - Hidden Truth in Recurrence

Post by Revenger »

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]

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Code: Select all

if (n + k + t <= 0) break;
Change it to:

Code: Select all

if ( n == 0 && k == 0 && t == 0 )
Or something. Your attempt to try to be slick made n + k overflows long long, and thus prematurely terminates.

here's my input:

Code: Select all

1234 1234 4
2323 99999999999 8
4 99999 9
888 888 8
900000000000000000 9000000000000000000 1
10 10 9
5 100 5
1 200 5
5 2 4
2 10 10
99999999999 3 8
5 6 9
0 0 0

Code: Select all

Case #1: 736
Case #2: 39087387
Case #3: 494777344
Case #4: 91255296
Case #5: 0
Case #6: 0
Case #7: 40625
Case #8: 1
Case #9: 25
Case #10: 1024
Case #11: 99999999
Case #12: 15625
Actually, I used unsigned long long, so maybe that's it..

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger »

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]

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn »

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

sharklu2000
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

Post by sharklu2000 »

if (b[n]) d = (d * k) % m;
change it to d= (d * (k%m)) % m, since d * k may exceed 64 bit range.
Aspire to AC.

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger »

Thanks, I get AC 8)

tep
New poster
Posts: 23
Joined: Fri Jun 13, 2003 6:08 am
Contact:

Post by tep »

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

regards,
stephanus

Post Reply

Return to “Volume 105 (10500-10599)”