SPOJ.com - Problem SUMPRO

SUMPRO - SUM OF PRODUCT

#simple-math #numbe

Given a number N, find the sum of all products x * y such that N / x = y (integer division).

Since the sum can be very large, please output this modulo 1000000007.

Input

The first line of input file contains an integer T, the number of test cases to follow. Each of the next T lines contain an integer N.

Output

Output T lines containing the answer to corresponding test case.

Example

Input:
3
2
4
6

Output:
4
15
33

Constraints:

1 ≤ T ≤ 500
1 ≤ N ≤ 10⁹

Explanation

Case #1:

2 / 1 = 2
2 / 2 = 1
Answer = 1 * 2 + 2 * 1 = 4

Case #2:

4 / 1 = 4
4 / 2 = 2
4 / 3 = 1
4 / 4 = 1
Answer = 1 * 4 + 2 * 2 + 3 * 1 + 4 * 1 = 15

Submit solution!

hide comments

< Previous 1 2 3 4 5 Next >

	Vaporeon: 2015-05-25 21:52:08 Awesome Maths here!! loved it! :D :* D:
	Amitayush Thakur: 2015-05-19 06:30:01 Think of O(n) solution first and then think of O(sqrt(n)) . Directly jumping over the O(sqrt(n)) solution will not help.
	Szymon: 2015-04-14 10:34:25 my solution works perfect for all numbers ... instead of {3,8,15,24} ;) I cheated lil bit and got AC, but don't want to investigate why it doesn't handle those 4 inputs
	rafiki93: 2015-04-12 18:24:08 @ivar.raknahs, I can't seem to login to the forum, hence posting my question here. Can you check my code, submission id: 14081284, and let me know which corner case my code doesn't handle. All test cases openly available passed. please help a little. Last edit: 2015-04-12 19:32:34
	Juan Carlos Arocha: 2015-02-20 05:01:41 akshaych dividing unsigned integers is faster than dividing signed integers (http://en.wikibooks.org/wiki/Optimizing_C%2B%2B/Code_optimization/Faster_operations#Integer_division_by_a_constant) reply-> thanks for sharing the information. Last edit: 2015-02-24 03:47:14
	akshaych: 2015-02-19 20:53:03 long long -> TLE long long unsigned -> AC..,Don't know why..!! However,it ruined my day..!! :( :(
	rishu: 2015-02-02 17:45:44 ivar.raknahs i got AC. but i am not satisfied with my solution. as there are many better solution. Just curious to know .. is there any better algo which can find in less than O(sqrt(n)). (Francky) ⇒ Mine is O(sqrt(n)) too, but I use div, mod and sqrt as few as possible. Last edit: 2015-02-02 17:55:44
	sahil hindwani: 2015-02-01 21:17:04 can u pls tell me the ans for 10^9 re(vamsi): my AC solution outputs 355091432 Last edit: 2015-02-03 08:05:33
	Raj Kumar Chauhan: 2015-01-31 12:33:59 anyone help me, why TLE? [Link removed] re(vamsi): don't post your code here(use forum) you obviously need a better algorithm than that Last edit: 2015-01-31 13:04:20
	:?ToRpiDo: 2015-01-26 13:43:03 @ivar.raknahs some tricky cases...plz --reply--> sorry ,no more test cases will be provided. Last edit: 2015-01-27 05:36:00

Submit solution!

Added by:	ivar.raknahs
Date:	2015-01-23
Time limit:	1s-1.5s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All
Resource:	Own