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 >

	mehmetin: 2015-01-29 17:41:22 Huge difference between my AC times with PYPY and Python 2.7, submitting the same code. Last edit: 2015-01-29 17:42:42
	foureC: 2014-10-01 15:53:49 Can someone please give more test cases? --ans(Francky)--> No other test case is provided. Good luck. Last edit: 2014-10-02 23:45:24
	Ayush Rajoria: 2014-02-01 19:31:19 My 100th problem !!!
	Yashpal: 2013-07-04 17:56:20 Getting TLE & runtime error yet i used O(n^.5).... <snip> i m new in python...help!! Last edit: 2023-06-06 22:51:48
	Mohit Gupta: 2013-06-27 16:38:20 my solution id is 9562986 this solution gets AC in problem AFS but gives WA for this problem cant understand why :( --ans--> Only WA on some cases. You're near. ----(mohit)--> Got AC!!! Thanks.. :) Last edit: 2013-07-01 05:18:36
	fR0DDY: 2013-06-13 14:07:49 My solution passes the time limit but I still think there are improvements. Can you give any hint? --ans--> The complexity of your method is quite good, please consider basic tip : use 'xrange' instead of 'while' loops, and read basic (general) python methods ; Google is your friend. Last edit: 2013-06-13 15:48:47
	[Lakshman]: 2013-05-11 16:38:49 Finally DONE ...feeling great after solving this...Don't know why getting incorrect answer with python...very poor in python... --ans--> Good job, the problem is not easy. ----Very Good problem....Took too much time to come up with this solution... Last edit: 2013-05-11 21:56:39
	Hardik: 2013-03-30 17:40:57 How to handle overflow ????? --ans--> Build your own container, or change your language. Last edit: 2013-03-30 17:53:47
	darkshadows: 2013-03-25 05:29:30 well i have a sqrt(n) algo. coded in python... but i am getting TLE..... as author said some optimizations with slower languages would be required... what kind of optimization? --ans(francky)--> First, you compute several times the same thing, here is a basic 'opti', you will perhaps need some others. (lalit)-->code with 100 test cases for worst case runs in 8 sec on my machine and considering the cluster is cube, still i get TLE!! Last edit: 2013-03-25 10:23:01
	Abhilash Kumar: 2013-03-24 09:46:26 --ans(francky)--> You have to check that with the given constraints. Good luck. done :) Last edit: 2013-03-25 18:57:09

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