DIVCNT3 - Counting Divisors (cube)
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_3(n) = \sum _{i=1}^n \sigma_0(i^3).$$
Given $N$, find $S_3(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^{11}$)
Output
For each number $N$, output a single line containing $S_3(N)$.
Example
Input
5
1
2
3
10
100
Output
1
5
9
73
2302
Explanation for Input
- $S_3(3) = \sigma_0(1^3) + \sigma_0(2^3) + \sigma_0(3^3) = 1 + 4 + 4 = 9$
Information
There are 5 Input files.
- Input #1: $1 \le N \le 10000$, TL = 1s.
- Input #2: $1 \le T \le 300,\ 1 \le N \le 10^{8}$, TL = 20s.
- Input #3: $1 \le T \le 75,\ 1 \le N \le 10^{9}$, TL = 20s.
- Input #4: $1 \le T \le 15,\ 1 \le N \le 10^{10}$, TL = 20s.
- Input #5: $1 \le T \le 2,\ 1 \le N \le 10^{11}$, TL = 20s.
My C++ solution runs in 7.1 sec. (total time)
Source Limit is 12 KB.
hide comments
Min_25:
2018-01-11 17:40:23
@zimpha: Probably, my solution runs in $O(n^{2/3+\epsilon})$ time (and uses a similar formula as yours).
|
|
zimpha:
2018-01-11 15:33:31
@Min_25, what is the time complexity of your solution. I use an O(n^(2/3)) method, but I still cannot run as fast as you can. |
|
Abhay Pratap:
2015-01-17 20:30:17
compiler was running up to case 5, then showed time limit exceeded...does it means only case 5 is not in the time_limit? |
|
TURTLE:
2014-10-19 11:11:41
@Min_25- Please give some hints about the question. Its been a while and the question is yet unsolved! Thanks in advance.
|
Added by: | Min_25 |
Date: | 2014-06-29 |
Time limit: | 1s-20s |
Source limit: | 12288B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |