SPOJ 1798. Assistance Required

http://www.spoj.com/problems/ASSIST/

 I suggest solving this task with precomputation. We can write a simple solution which can find the numbers for us and write those numbers in am output file in the way so that we can use them in our source file. Here is my solution with C++ with the process of counting the numbers and also the main source code.

       DOWNLOAD THE FULL SOURCE CODE

SPOJ 14138. Amazing Factor Sequence

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.

   DOWNLOAD THE FULL SOURCE CODE