This is the problem statement
http://www.spoj.com/problems/AFS/
This problem is very tricky. let's have a look at constraints
n<=1000000
t<=100
This task will take a lot of time even if we tried calculating the answer for N=1000000 even if used powerful math. And the number of test cases makes it worse. For dealing with test cases we need to make precalculations. Remember the sieve of Eratosfen? We looped over our array and checked if we have one prime number we mark all the numbers which are divisible to the found number as not prime. We will use almost the same approach but with the divisors ;). The problem defines some function f(n) which is equal to sum of divisors of n. We will keep an array . The I th element will show the f(I) . Now we loop over our array. Suppose we are now at the spot I. We are sure that the numbers 2*I , 3*I , 4*I, 5*I ..... all will have the divisor I so we can add the value I to the elements a[2*I], a[3*I], a[4*I]...... using this method we found all the values of function f with the speed of a little bit more than NlogN Now we need to keep an array of answers and to keep the answers up to1000000. This can be done easily in O(N) time. Now for the test cases. Now that we have calculated all the values, we are ready to read the input and output the answer right away.
http://www.spoj.com/problems/AFS/
This problem is very tricky. let's have a look at constraints
n<=1000000
t<=100
This task will take a lot of time even if we tried calculating the answer for N=1000000 even if used powerful math. And the number of test cases makes it worse. For dealing with test cases we need to make precalculations. Remember the sieve of Eratosfen? We looped over our array and checked if we have one prime number we mark all the numbers which are divisible to the found number as not prime. We will use almost the same approach but with the divisors ;). The problem defines some function f(n) which is equal to sum of divisors of n. We will keep an array . The I th element will show the f(I) . Now we loop over our array. Suppose we are now at the spot I. We are sure that the numbers 2*I , 3*I , 4*I, 5*I ..... all will have the divisor I so we can add the value I to the elements a[2*I], a[3*I], a[4*I]...... using this method we found all the values of function f with the speed of a little bit more than NlogN Now we need to keep an array of answers and to keep the answers up to1000000. This can be done easily in O(N) time. Now for the test cases. Now that we have calculated all the values, we are ready to read the input and output the answer right away.
No comments:
Post a Comment