SPOJ.com - Problem AFS

AFS - Amazing Factor Sequence

no tags

Bhelu is the classmate of Bablu who made the Amazing Prime Sequence.

He felt jealous of his classmate and decides to make his own sequence. Since he was not very imaginative, he came up with almost the same definition just making a difference in f(n):

a[0] = a[1] = 0.
For n > 1, a[n] = a[n - 1] + f(n), where f(n) is the sum of positive integers in the following set S.
S = {x | x < n and n % x = 0}.

Now, Bablu asked him to make a code to find f(n) as he already had the code of his sequence. So, Bhelu asks for your help since he doesn't know programming. Your task is very simple, just find a[n] for a given value of n (< 10^6).

Input

Your code will be checked for multiple test cases.

First Line of Input contains T (<= 100), the number of test cases.

Next T lines contain a single positive integer N. (1 < N < 10^6).

Output

Single line containing a[n] i.e. n-th number of the sequence for each test case.

Example

Input:
3
3
4
5

Output:
2
5
6

Explanation

f(2) = 1 {1}
f(3) = 1 {1}
f(4) = 3 {1, 2}
f(5) = 1 {1}

Submit solution!

hide comments

< Previous 1 2 3 Next >

	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-03-16 19:25:52 solved using 12 different(?) programming language, haha :-D First time I do that on SPOJ... ;-)
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-03-16 16:14:14 aaa! I'm late... I never imagine that O(sqrt(n)) exists... I should think out of the box to notice that... I still think that time limit is too relaxed, problemsetter should change that to 1s.. --ans(francky)--> No, I think this one should land in tutorial, I propose Robert Gerbicz (honor is him) to set a new one with much higher limit as the classical one. A new edition that allows python solutions but not 'bad' C-ones. Re(Tjandra): Ok, up to you... I hope the new one doesn't need BigNum operation... e.g output modulo something 32-bit number :-) Last edit: 2013-03-16 17:18:18
	Francky: 2013-03-16 11:39:04 Oh Oh, it seems Robert Gerbicz shows us that a Python solution will be possible. Good news, and great challenge. Edit : challenge done ! ;-), and 0.01s in C (with basic IO). Last edit: 2013-03-16 14:36:15
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-03-16 05:37:29 I wonder if 3s time limit is too long/relax (for C/C++ user)? AC in 0.25s without fast I/O.. My solution is approx O(nlog(n)) --ans(francky)--> I agree with your remark, it was the meaning of my comment ; a poor C-code can get AC whereas a good python one have no chance. And with 100 cases, obviously it's not I/O related, the problem is not here. That's why my feeling is not so good for those problems. :-( But reduce the limit time is neither a good solution, and hard to decide the "good" time... Re(Tjandra): Now I'm sure* that this problem in tutorial, my last submission with approx O(nsqrt(n)) (no precomputation!) got accepted in 2.56s! this problem is trivial.. Imho, the TL should be at least 1.50s to keep in classical and reject approx O(nsqrt(n)) solution, the "good" solutution should be at least approx O(nlog(n)).. See also my Smallest Inverse Sum of Divisors problem that only accept solution at least approx O(nlog(n)).. Last edit: 2013-03-16 10:48:09
	Shaily Mittal: 2013-03-15 20:23:45 @Francky: What is the complexity of the code? --ans--> various solutions -> various answer. Those of a sieve for example. Last edit: 2013-03-15 21:19:35
	Francky: 2013-03-15 16:29:11 My all first (very poor) C-code (15-01-2012) for DIVSUM, with minor modifications, can get AC. And I bet it will very hard or quite impossible to get AC in Python. :-( I wonder if AFS and APS are tutorial or not, but good ones. Edit : I loose my bet. ;-) Last edit: 2013-03-16 14:37:28

Submit solution!

Added by:	c[R]@zY f[R]0G
Date:	2013-03-15
Time limit:	1s
Source limit:	5000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64