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]:
2018-01-25 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.
|
|
cabbby:
2016-05-17 03:00:55
@Min_25 Could I know your email?
|
|
hemant kumar:
2016-01-17 16:15:03
please provide tutorial for this problem |
|
Fionsel:
2014-10-19 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:
2014-10-19 11:09:53
probably something like the following would cure precision issues:
|
|
wellwet:
2014-10-19 11:09:53
@Mitch: round(), cbrtf() and cbrtl() don't get AC but adding 1e-9 does the trick! Last edit: 2014-07-04 05:31:40 |
|
Mitch Schwartz:
2014-10-19 11:09:53
Hmm, for (long long)cbrt(13*13*13) on Cube cluster I get 13. The "completely broken" claim is probably false. We should of course expect precision issues for sufficiently large numbers. @wellwet did you also try: (1) adding 0.5 before casting (or subtracting 0.5 if negative), or using round(), if applicable; (2) using cbrtl() ? Note that cbrtf() is less precise than cbrt()...
|
|
|
wellwet:
2014-10-19 11:09:53
@Min_25: please check your test cases. Got WA but the same algo in PARI as long as naive div counting gives the same results. Or point that test case which gives WA. BTW, complexity can be reduced to O(n^(5/9)).
|
|
RIVU DAS:
2014-10-19 11:09:53
@Min_25 - What is your complexity??
|
| 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 |
RSS