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]: 2024-01-01 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: 2023-04-10 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: 2023-03-29 17:20:27

Is $O(n^{3/4})$ supposed to pass ?
EDIT: I guess for both DIVCNT2 and DIVCNT3 $O(n^{3/4})$ passes even though author's intended solution is $O(n^{2/3})$ .Asymptotic difference between $O(n^{3/4})$ and $O(n^{2/3})$ is about 10x but practically the implementation would be 3x-4x faster.In DIVCNT1 it was easier to restrict weaker solution as the difference between $O(n^{1/2})$ and $O(n^{1/3})$ asymptotically itself is 1000x. [PS:I am ignoring all log terms for sake of simplicty of discussion]

Last edit: 2023-03-30 05:01:17
deannos: 2022-08-02 17:27:06

but i got wrong answer????????????

<snip>
[Simes]: Read the footer - Don't post source code here, use the forum.

Last edit: 2022-08-02 21:35:11
jacobian_det: 2020-04-20 12:15:11

How to improve running time of my solution @Min_25?
ID - 25810071

userhacker_1: 2018-03-15 13:20:41

for exmple we can get Divisor Summatory Function in O(n​1/3​​logn)(DIVCNT1) instead O(√​n​​​) .... it improve time? (Re) Yes for some ranges.

Last edit: 2018-03-15 13:44:25
userhacker_1: 2018-03-15 10:53:45

wow. how some user solved it in 3 sec? or they solved partially?
(Re) Their solutions solved all. There are various solutions for this problem.

Last edit: 2018-03-15 13:15:35
userhacker_1: 2018-03-15 10:50:06

what is you mean from total time? time sum of all input?
(Re) Yes.

Last edit: 2018-03-15 13:04:19
[Lakshman]: 2018-01-25 07:55:42

Thanks, @Min_25 for clarification. Just to confirm is it about my Submission-ID 21047354.

(Re) $D(n/i)$ runs in $O(\sqrt{n/i})$ time. So, the same argument can be applied.

Last edit: 2018-01-26 09:12:50
Min_25: 2018-01-25 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: 2018-01-25 07:06:44

Added by:Min_25
Date:2014-06-29
Time limit:1s-20s
Source limit:6144B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU