## 11029 - Leading and Trailing

Moderator: Board moderators

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

### 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?
kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
Let C = A^B,

lg(C) = B*lg(A), lg - decimal logarithm lg(x) = ln(X)/ln(10).
First three digits of C are first three digits of mantissa of lg(C).

That's how I got AC (not sure about mathematical correctness).
jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
and how about the three last digits ???
kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
A^B mod 1000
trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru
kp: thx very much for helping.
jan holmes:for last 3 digits you can use logarithmic exponentiation.
helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Can anybody check this out..?
I'm getting WA..

Code: Select all

``````CUT AFTER AC
``````
Last edited by helloneo on Sat May 13, 2006 8:31 pm, edited 1 time in total.
kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Code: Select all

``````  temp1 = temp1 - temp2 + 4.0;
temp3 = pow(10.0, temp1);
sprintf(buf1, "%.0Lf", temp3);
``````
with this:

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);
``````
lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm
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 ^^
helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
kp and lonelyone ..
Thanks for help.. I got AC..

Actually I already solved the problem 374 ..
but didn't notice this is about big mod .. ^_^;
jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Code: Select all

``````AC...ed :D
``````
Thx...
Last edited by jan_holmes on Sun May 14, 2006 7:34 am, edited 3 times in total.
kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
It's because of overflow

Replace

Code: Select all

``````return (pangkat(search(a,b/2))%1000*a%1000)%1000;
``````
with

Code: Select all

``````return (pangkat(search(a,b/2))%1000*(a%1000))%1000;
``````
or

in the main program use

Code: Select all

``````search(a%1000,b)
``````

Code: Select all

``````search(a,b)
``````
jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
Thx kp,but I still got WA... Please give me critical I/O... thx...
kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
2100000056 67333

982...016

983...016

...

see my third post at this topic
helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Code: Select all

``````...
``````
Thx...
Hello..~
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.
mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:

Code: Select all

``temp1 = temp1-temp2+4.0;``
You can increase this constant 4.0 to say, 5.0.