SPOJ.com - Problem AFS2

AFS2 - Amazing Factor Sequence (medium)

no tags

Warning

Here is a harder version of Amazing Factor Sequence .

To make things clear, you'll need a O(n^0.5) method to solve this problem. You'll need to be careful with container of C-like language, and/or you'll need to find some little optimizations with slower language.

The factor sequence

We define our factor sequence with:

a[0] = a[1] = 0, and

for n > 1, a[n] = a[n - 1] + sum({x | x < n and n % x = 0}).

Input

First line of input contains an integer T, the number of test cases.

Each of the next T lines contains a single integer n.

Output

For each test case, print a[n] on a single line.

Example

Input:
3
3
4
5

Output:
2
5
6

Constraints

0 < T < 101
0 < n < 12148001999

Numbers n are uniform-randomly chosen. Nmax was carefully chosen ;-)
Time limit is ×2.5 my python one (2.56s). (Edited 2017-02-11, after compiler changes)

Submit solution!

hide comments

< Previous 1 2 Next >

	mahmud2690: 2016-10-19 20:35:19 Useless limit on N, be aware answer may not fit 64 bit unsigned int. Last edit: 2016-10-19 20:36:23
	hm_98: 2016-06-24 13:20:36 Getting AC in AFS, but getting WA in AFS2. I have used unsigned long long for the variables. What are the possible reasons? =(Francky)=> You could have overflow errors on some cases... You should check the hardest case step by step. Last edit: 2016-06-24 13:26:24
	karthik1997: 2016-06-23 18:47:05 @ Francky .. Can you please see my solution . I have solved it on the assumption of a theoretical solution and Im getting TLE and my submission id : 17165398 .. Link for that : **************no link ; please ***** =(Francky)=> Did you checked with all small values and a brute force solutions ? Did you checked with some high input numbers ? The complexity of your code looks good, but could have some bugs. Good luck. Last edit: 2016-06-23 19:33:55**
	Piyush Kumar: 2016-05-28 08:55:04 Wow! The code that timed out in Python got AC in PyPy
	MD AKBAR: 2015-09-30 18:44:35 sir,i am not getting how to cope with overflow of long long in C lang..........same code accepted in pypy....... is it possible in C or not ?? submission id 15254755. =(Francky)=> Just have a look at ranking... Last edit: 2015-10-05 17:17:05
	ANIKET: 2015-08-28 16:04:22 Nice question Last edit: 2015-09-17 15:34:55
	xMAn: 2015-08-22 08:42:39 what is the ans for ******** =(Francky)=> No other case is provided Last edit: 2015-08-22 09:38:31**
	Shubham Shukla: 2015-07-11 11:43:34 Is this question solvable in c?? Did it using python
	harkirat: 2015-06-05 12:28:45 could you check my solution? it it right for the first 100000 cases 14397074 =(Francky)=> You output some negative numbers, you should have seen that ! Last edit: 2015-06-05 19:09:51
	Maroof: 2015-05-25 10:51:46 @Francky Can you please let me know, what's wrong with my solution. it's giving correct answer for the test cases upto the limit but still WA... submission id is 14317359 =(Francky)=> It seems you get AC now. Well done. Last edit: 2015-06-05 19:11:39

Submit solution!

Added by:	Francky
Date:	2013-03-16
Time limit:	6.400s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	AFS