AFS2  Amazing Factor Sequence (medium)
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 Clike 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 uniformrandomly chosen. Nmax was carefully chosen ;)
Time limit is ×2.5 my python one (2.56s). (Edited 20170211, after compiler changes)
hide comments
mahmud2690:
20161019 20:35:19
Useless limit on N, be aware answer may not fit 64 bit unsigned int. Last edit: 20161019 20:36:23 

hm_98:
20160624 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?


karthik1997:
20160623 18:47:05
@ Francky .. Can you please see my solution . I have solved it on the assumption of a theoretical solution


Piyush Kumar:
20160528 08:55:04
Wow! The code that timed out in Python got AC in PyPy 

MD AKBAR:
20150930 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.


ANIKET:
20150828 16:04:22
Nice question


xMAn:
20150822 08:42:39
what is the ans for **********


Shubham Shukla:
20150711 11:43:34
Is this question solvable in c?? Did it using python 

harkirat:
20150605 12:28:45
could you check my solution?


Maroof:
20150525 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

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