## 10990 - Another New Function

Moderator: Board moderators

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

### 10990 - Another New Function

What method should we use in this problem ??? I use sieve... but still TLE... How to make it faster ??? Thx...

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
How do you use the sieve, and what do you use it for? What is the time complexity of answering a single query in your solution?

If N is the largest possible input number, my solution precomputes data in O(N log N) and answers queries in O(1).

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
Can I precompute all phi(1) to phi(N) values in O(N lgN) time?
Sorry For My Poor English..

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Yes, you can.
If only I had as much free time as I did in college...

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
hmm..

Anybody please, give me some hints for approaching computation of phi(1 to N) in order that its time-complexity may be O(n logn).
I can't easily find clear one!
Sorry For My Poor English..

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Do you know how to factor the numbers from 1 to N in O(NlogN) time? It's a simple modification to the standard Sieve of Erastosthenes. That's a start.

The next step is to look at the formula for phi(n) that uses the factorization of n.
If only I had as much free time as I did in college...

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
I got the picture by a simple modification of the sieve of Erastosthenes.
It is very simple idea, and now I finally knew how to do that.

Thank you very much, Abednego.
Sorry For My Poor English..

frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:
Sorry,But could you tell me how to modify the sieve of Erastosthenes?
I try to modify it in order to get the factorization of n but get MLE.
So could you show me the picture? Thx!!

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
The Memory complexity of modified-sieve-algorithm (for factorization of integers) should be O(N), not O(N lgN).
(I used just 4 arrays of size 2000000, and used memory is almost 30000.
You shouldn't use more than 4 linear-arrays, or you'll get MLE.)

for each integer v ∈ [1...N],
store the prime factor factor[v] that divides v.

And, another hint :
factorization of 72 can refer factorization of 9, if factor[72] is 2.
Sorry For My Poor English..

frankhuhu
New poster
Posts: 30
Joined: Tue Jul 20, 2004 5:22 am
Contact:
I have made a silly mistake and get AC now!!
Andway thanks a lot !!

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan
what should the test case be?
2
2 2000000
72 72

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
polone wrote:what should the test case be?
2
2 2000000
72 72
Output from my AC program:

Code: Select all

``````33829803
5
``````

greather
New poster
Posts: 2
Joined: Mon Feb 13, 2006 5:58 pm
Location: korea
Contact:

### Sample Input case plz.....

plz show me various sample input and output case ......
ah!

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm
sorry, but I want to know why I couldn't see the pictures in this problems?
could anyone tell me why.. appreciate ^^"

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

There are some problems in the links to the images in UVa's problems occasionally. Or you can view the pdf files.