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 ?
|
|
deannos:
2022-08-02 17:27:06
but i got wrong answer????????????
|
|
jacobian_det:
2020-04-20 12:15:11
How to improve running time of my solution @Min_25?
|
|
userhacker_1:
2018-03-15 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: 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?
|
|
userhacker_1:
2018-03-15 10:50:06
what is you mean from total time? time sum of all input?
|
|
[Lakshman]:
2018-01-25 07:55:42
Thanks, @Min_25 for clarification. Just to confirm is it about my Submission-ID 21047354.
|
|
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 |