11029  Leading and Trailing
Moderator: Board moderators
11029  Leading and Trailing
how to get the first tree digits? Can this be done in O(logn), i mean, is it realted with modular exponentiation?

 Experienced poster
 Posts: 136
 Joined: Fri Apr 15, 2005 3:47 pm
 Location: Singapore
 Contact:
Last edited by helloneo on Sat May 13, 2006 8:31 pm, edited 1 time in total.
Try to replace your part:
with this:
Code: Select all
temp1 = temp1  temp2 + 4.0;
temp3 = pow(10.0, temp1);
sprintf(buf1, "%.0Lf", temp3);
Code: Select all
temp1 = temp1  temp2;
temp3 = pow(10.0, temp1);
while (temp3<1000.0) temp3 *= 10.0;
int tmp = floor(temp3);
while (tmp>999) tmp /= 10;
sprintf(buf1, "%d", tmp);
I don't think so, all of yours are right.
I think the bug of helloneo's code is in finding last three digits.
Did you know logarithm of finding n^k algorithm?
If you have no idea, you could reference it in Intro. to Algorithm.
Similar idea in UVa374, if you solved this problem.
You could use same thought to solve logarithm of it.
Hope this helps.
Lonely ^^
I think the bug of helloneo's code is in finding last three digits.
Did you know logarithm of finding n^k algorithm?
If you have no idea, you could reference it in Intro. to Algorithm.
Similar idea in UVa374, if you solved this problem.
You could use same thought to solve logarithm of it.
Hope this helps.
Lonely ^^

 Experienced poster
 Posts: 136
 Joined: Fri Apr 15, 2005 3:47 pm
 Location: Singapore
 Contact:
I'm using this method,but I got WA... Please Help :
Thx...
Code: Select all
AC...ed :D
Last edited by jan_holmes on Sun May 14, 2006 7:34 am, edited 3 times in total.
It's because of overflow
Replace
with
or
in the main program use
instead of
Replace
Code: Select all
return (pangkat(search(a,b/2))%1000*a%1000)%1000;
Code: Select all
return (pangkat(search(a,b/2))%1000*(a%1000))%1000;
in the main program use
Code: Select all
search(a%1000,b)
Code: Select all
search(a,b)

 Experienced poster
 Posts: 136
 Joined: Fri Apr 15, 2005 3:47 pm
 Location: Singapore
 Contact:
Hello..~jan_holmes wrote:I'm using this method,but I got WA... Please Help :
Thx...Code: Select all
...
I got WA with that code too..
Don't know why it doesn't work.. possibly precision error..
Replace that part with what kp suggested.. ~
Last edited by helloneo on Sun May 14, 2006 7:50 am, edited 1 time in total.
Code: Select all
temp1 = temp1temp2+4.0;