DIVCNT2  Counting Divisors (square)
Let $\sigma_0(n)$ be the number of positive divisors of $n$.
For example, $\sigma_0(1) = 1$, $\sigma_0(2) = 2$ and $\sigma_0(6) = 4$.
Let $$S_2(n) = \sum _{i=1}^n \sigma_0(i^2).$$
Given $N$, find $S_2(N)$.
Input
First line contains $T$ ($1 \le T \le 10000$), the number of test cases.
Each of the next $T$ lines contains a single integer $N$. ($1 \le N \le 10^{12}$)
Output
For each number $N$, output a single line containing $S_2(N)$.
Example
Input
5
1
2
3
10
100
Output
1
4
7
48
1194
Explanation for Input
 $S_2(3) = \sigma_0(1^2) + \sigma_0(2^2) + \sigma_0(3^2) = 1 + 3 + 3 = 7$
Information
There are 6 Input files.
 Input #1: $1 \le N \le 10000$, TL = 1s.
 Input #2: $1 \le T \le 800,\ 1 \le N \le 10^{8}$, TL = 20s.
 Input #3: $1 \le T \le 200,\ 1 \le N \le 10^{9}$, TL = 20s.
 Input #4: $1 \le T \le 40,\ 1 \le N \le 10^{10}$, TL = 20s.
 Input #5: $1 \le T \le 10,\ 1 \le N \le 10^{11}$, TL = 20s.
 Input #6: $T = 1,\ 1 \le N \le 10^{12}$, TL = 20s.
My C++ solution runs in 5.3 sec. (total time)
Source Limit is 6 KB.
hide comments
[Lakshman]:
20240101 06:28:42
@Ishan I was not active on SPOJ for long, Yes, I was wrong in calculating the complexity Min_25 is right. 

Ishan:
20230410 04:15:39
@Lakshman If you have really solved it in $O(n^{1/2})$ you will be making a grand new breakthrough worthy of Turing Award many times over. I am sure you have some miscalculation. 

Ishan:
20230329 17:20:27
Is $O(n^{3/4})$ supposed to pass ?


deannos:
20220802 17:27:06
but i got wrong answer????????????


jacobian_det:
20200420 12:15:11
How to improve running time of my solution @Min_25?


userhacker_1:
20180315 13:20:41
for exmple we can get Divisor Summatory Function in O(n1/3logn)(DIVCNT1) instead O(√n) .... it improve time? (Re) Yes for some ranges. Last edit: 20180315 13:44:25 

userhacker_1:
20180315 10:53:45
wow. how some user solved it in 3 sec? or they solved partially?


userhacker_1:
20180315 10:50:06
what is you mean from total time? time sum of all input?


[Lakshman]:
20180125 07:55:42
Thanks, @Min_25 for clarification. Just to confirm is it about my SubmissionID 21047354.


Min_25:
20180125 07:05:54
@[Lakshman]: It is not $O(\sqrt{n})$ but $O(n^{2/3})$ since $\int_{1}^{\sqrt[3]{n}} \sqrt{n/x}\, dx \in \Theta(\sqrt{n} \cdot n^{1/6}) = \Theta(n^{2/3})$. Last edit: 20180125 07:06:44 
Added by:  Min_25 
Date:  20140629 
Time limit:  1s20s 
Source limit:  6144B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 