10990  Another New Function
Moderator: Board moderators

 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...
The Memory complexity of modifiedsievealgorithm (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 lineararrays, 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 used just 4 arrays of size 2000000, and used memory is almost 30000.
You shouldn't use more than 4 lineararrays, 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..
Output from my AC program:polone wrote:what should the test case be?
2
2 2000000
72 72
Code: Select all
33829803
5