DIVCNT1 - Counting Divisors
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_1(n) = \sum _{i=1}^n \sigma_0(i).$$
Given $N$, find $S_1(N)$.
Input
First line contains $T$ ($1 \le T \le 100000$), the number of test cases.
Each of the next $T$ lines contains a single integer $N$. ($1 \le N < 2^{63}$)
Output
For each number $N$, output a single line containing $S_1(N)$.
Example
Input
5
1
2
3
10
100
Output
1
3
5
27
482
Explanation for Input
- $S_1(3) = \sigma_0(1) + \sigma_0(2) + \sigma_0(3) = 1 + 2 + 2 = 5$
Information
There are 6 input files.
- Input #1: $1 \le N \le 100000$, TL = 2s.
- Input #2: $1 \le T \le 120,\ 1 \le N \le 10^{15}$, TL = 15s.
- Input #3: $1 \le T \le 60,\ 1 \le N \le 10^{16}$, TL = 15s.
- Input #4: $1 \le T \le 25,\ 1 \le N \le 10^{17}$, TL = 15s.
- Input #5: $1 \le T \le 10,\ 1 \le N \le 10^{18}$, TL = 15s.
- Input #6: $1 \le T \le 5,\ 1 \le N < 2^{63}$, TL = 15s.
My C++ solution runs in about 1.3 seconds for each input #2 - #6.
Note
- Probably, $O(\sqrt{n})$ solutions will not pass.
- Intended solutions have a running time of about $O(n^{1/3} \log n)$.
- The answer can be $\ge 2^{64}$.
hide comments
userhacker_1:
2018-03-16 16:15:28
thanks good problem ;\ Last edit: 2018-03-16 19:04:23 |
|
Min_25:
2017-11-09 04:43:17
@Blue.Mary
|
|
[Rampage] Blue.Mary:
2017-11-08 02:31:15
Maybe this paper helps? https://arxiv.org/abs/1206.3369. |
|
Min_25:
2017-11-07 23:31:46
@dacin21:
|
|
dacin21:
2017-11-07 21:16:12
@Min_25 This is a really beautiful problem, thanks a lot for posting it.
|
Added by: | Min_25 |
Date: | 2015-12-30 |
Time limit: | 2s-15s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |