Posted:

**Wed Jun 13, 2007 6:40 pm**Thanks..

Got AC..~

Got AC..~

The Online Judge board

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

https://uva.onlinejudge.org/board/viewtopic.php?f=38&t=18180

Page **2** of **2**

Posted: **Wed Jun 13, 2007 6:40 pm**

Thanks..

Got AC..~

Got AC..~

Posted: **Wed Jun 13, 2007 6:55 pm**

can anybody check it for me?

Code: Select all

```
Input:
49
2 10
11 20
90000 4560
489000 94561
334142 334142
334143 500000
2 334141
2 100000
100000 200000
200000 300000
300000 400000
400000 500000
2 100
100 200
200 300
300 400
400 500
500 600
600 700
700 800
800 900
900 1000
1000 1100
1100 1200
1200 1300
1300 1400
1400 1500
1500 1600
1600 1700
1700 1800
1800 1900
1900 2000
2000 2100
2100 2200
2200 2300
2300 2400
2400 2500
2500 2600
2600 2700
2700 2800
2800 2900
2900 3000
3000 3100
3100 3200
3200 3300
3300 3400
3400 3500
3500 3600
3600 3700
Output:
Case #1:
3
Case #2:
4
Case #3:
12
Case #4:
14
Case #5:
14
Case #6:
12
Case #7:
13
Case #8:
12
Case #9:
13
Case #10:
12
Case #11:
14
Case #12:
12
Case #13:
6
Case #14:
7
Case #15:
7
Case #16:
8
Case #17:
8
Case #18:
7
Case #19:
8
Case #20:
7
Case #21:
8
Case #22:
8
Case #23:
8
Case #24:
7
Case #25:
9
Case #26:
7
Case #27:
7
Case #28:
9
Case #29:
7
Case #30:
9
Case #31:
8
Case #32:
9
Case #33:
8
Case #34:
7
Case #35:
8
Case #36:
8
Case #37:
8
Case #38:
9
Case #39:
9
Case #40:
8
Case #41:
8
Case #42:
7
Case #43:
8
Case #44:
8
Case #45:
8
Case #46:
7
Case #47:
8
Case #48:
8
Case #49:
8
```

Posted: **Wed Jun 13, 2007 8:57 pm**

Your cases are correct.

Posted: **Thu Jun 14, 2007 4:25 am**

Thanks Jan!

but then, any other tricky I/Os?

really have no idea why keeping WA

but then, any other tricky I/Os?

really have no idea why keeping WA

Posted: **Thu Jun 14, 2007 9:50 am**

hello...

try these.

input
output

try these.

input

Code: Select all

```
10
2 2
3 2
2 3
2 100
100 101
300 300
1000 1000
10001 1000
500000 500000
100 500000
```

Code: Select all

```
Case #1:
1
Case #2:
1
Case #3:
1
Case #4:
6
Case #5:
5
Case #6:
2
Case #7:
4
Case #8:
11
Case #9:
3
Case #10:
14
```

Posted: **Thu Jun 14, 2007 3:08 pm**

ACed finally!

Very silly bug

thank you for all your helps!

Very silly bug

thank you for all your helps!

Posted: **Mon Jan 05, 2009 8:15 pm**

hi I am getting WA in this problem

please give some that can fix my code. I've already tested with all board I/O.
Thank's in advance.

please give some that can fix my code. I've already tested with all board I/O.

Code: Select all

```
Cur after AC
```

Posted: **Tue Jan 06, 2009 3:32 pm**

Ok, I found my bug. It was a silly one

Posted: **Wed May 06, 2015 1:14 am**

I got AC in 0.355s Without using shieve.

Fisrt- Found a way of factoring a number, I do the TRIAL DIVISION, (just like factoring by hand) anyway. I think that if you could do it in less time, would be great.

Given the factoring, computing alpha(n) is easy. (I did it in the same function)

Second, Memorize alpha and beta (Use dynamic programming) beta can be computed recursevely. the base case is when n==alpha(n), beta(n)=1 otherwise beta(n) = beta(alpha(n))+1

you memorize that so you don't have to re-compute all the stuff.

I saw that linear search is sufficent. so try it in the array "beta" generated.

But i tought that linear search wouldn't work so I made a "SEGMENT TREE". A segment tree is a wonderful datastructure which is iniatialized in O(n) and the querys are done in O( log(n) )

Hope this will help you.

I attach some useful links;:

Segment tree: http://www.geeksforgeeks.org/segment-tr ... mum-query/

Factoring and trial division: https://www.topcoder.com/community/data ... -function/

Dynamic Programing: https://www.youtube.com/watch?v=OQ5jsbhAv_M

Fisrt- Found a way of factoring a number, I do the TRIAL DIVISION, (just like factoring by hand) anyway. I think that if you could do it in less time, would be great.

Given the factoring, computing alpha(n) is easy. (I did it in the same function)

Second, Memorize alpha and beta (Use dynamic programming) beta can be computed recursevely. the base case is when n==alpha(n), beta(n)=1 otherwise beta(n) = beta(alpha(n))+1

you memorize that so you don't have to re-compute all the stuff.

I saw that linear search is sufficent. so try it in the array "beta" generated.

But i tought that linear search wouldn't work so I made a "SEGMENT TREE". A segment tree is a wonderful datastructure which is iniatialized in O(n) and the querys are done in O( log(n) )

Hope this will help you.

I attach some useful links;:

Segment tree: http://www.geeksforgeeks.org/segment-tr ... mum-query/

Factoring and trial division: https://www.topcoder.com/community/data ... -function/

Dynamic Programing: https://www.youtube.com/watch?v=OQ5jsbhAv_M