OJ Board

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

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

Can I precompute all phi(1) to phi(N) values in O(N lgN) time?

Yes, you can.

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!

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.

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,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!!

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.

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

what should the test case be?
2
2 2000000
72 72

polone wrote:what should the test case be?
2
2 2000000
72 72

Output from my AC program:

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

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

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