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)


hide comments
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

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