10990 - Another New Function

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10990 - Another New Function

Post by jan_holmes » Sat Feb 11, 2006 8:37 pm

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

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sat Feb 11, 2006 10:39 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

Post by wook » Sun Feb 12, 2006 4:46 am

Can I precompute all phi(1) to phi(N) values in O(N lgN) time?
Sorry For My Poor English.. :)

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun Feb 12, 2006 5:03 am

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

Post by wook » Sun Feb 12, 2006 7:52 am

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

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun Feb 12, 2006 8:03 am

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

Post by wook » Sun Feb 12, 2006 8:53 am

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:

Post by frankhuhu » Sun Feb 12, 2006 10:27 am

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

Post by wook » Sun Feb 12, 2006 10:40 am

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:

Post by frankhuhu » Sun Feb 12, 2006 11:34 am

I have made a silly mistake and get AC now!! :P
Andway thanks a lot !! :wink:

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Mon Feb 13, 2006 3:40 pm

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

Post by misof » Mon Feb 13, 2006 4:09 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.....

Post by greather » Mon Feb 13, 2006 6:02 pm

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

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Mon Feb 13, 2006 7:24 pm

sorry, but I want to know why I couldn't see the pictures in this problems?
could anyone tell me why.. appreciate ^^"

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

Post by Cho » Mon Feb 13, 2006 7:34 pm

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

Post Reply

Return to “Volume 109 (10900-10999)”