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

[Lakshman]:
20180125 06:48:30
@Min_25 Recently I come up with some sort of $O(\sqrt{n})$,and it is working fine here as well.See 21047354, although My old solution is $O(n^{2/3})$, I am surprised to see both are producing the result in approx same time. Last edit: 20180125 11:30:24 

cabbby:
20160517 03:00:55
@Min_25 Could I know your email?


hemant kumar:
20160117 16:15:03
please provide tutorial for this problem 

Fionsel:
20141019 11:09:53
Is it possible to give a one or more test cases of large numbers? I keep getting WA whereas I've verified (by brute force) my algorithm for numbers up to 1000 to be correct.


wisfaq:
20141019 11:09:53
probably something like the following would cure precision issues:

Added by:  Min_25 
Date:  20140629 
Time limit:  1s20s 
Source limit:  6144B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 