### 11029 - Leading and Trailing

Posted:

**Sat May 13, 2006 5:55 pm**how to get the first tree digits? Can this be done in O(logn), i mean, is it realted with modular exponentiation?

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=33&t=10638

Page **1** of **3**

Posted: **Sat May 13, 2006 5:55 pm**

how to get the first tree digits? Can this be done in O(logn), i mean, is it realted with modular exponentiation?

Posted: **Sat May 13, 2006 6:19 pm**

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).

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).

Posted: **Sat May 13, 2006 6:26 pm**

and how about the three last digits ???

Posted: **Sat May 13, 2006 7:03 pm**

A^B mod 1000

Posted: **Sat May 13, 2006 7:05 pm**

kp: thx very much for helping.

jan holmes:for last 3 digits you can use logarithmic exponentiation.

jan holmes:for last 3 digits you can use logarithmic exponentiation.

Posted: **Sat May 13, 2006 7:05 pm**

Posted: **Sat May 13, 2006 7:25 pm**

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);
```

Posted: **Sat May 13, 2006 7:36 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 ^^

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 ^^

Posted: **Sat May 13, 2006 8:39 pm**

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 .. ^_^;

Thanks for help.. I got AC..

Actually I already solved the problem 374 ..

but didn't notice this is about big mod .. ^_^;

Posted: **Sat May 13, 2006 9:26 pm**

I'm using this method,but I got WA... Please Help :

Thx...

Code: Select all

```
AC...ed :D
```

Posted: **Sat May 13, 2006 10:25 pm**

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)
```

Posted: **Sat May 13, 2006 10:40 pm**

Thx kp,but I still got WA... Please give me critical I/O... thx...

Posted: **Sat May 13, 2006 10:49 pm**

2100000056 67333

answer should be

982...016

your program get

983...016

...

see my third post at this topic

answer should be

982...016

your program get

983...016

...

see my third post at this topic

Posted: **Sun May 14, 2006 5:29 am**

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.. ~

Posted: **Sun May 14, 2006 6:50 am**

Code: Select all

`temp1 = temp1-temp2+4.0;`