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.

==> Sorry, I have to edit my comment.
This is really stupid comment from me. Indeed its is $O(n^{2/3})$,

Last edit: 2024-01-01 06:30:09
cabbby: 2016-05-17 03:00:55

@Min_25 Could I know your email?

(Re: Min_25)
Why ??

Last edit: 2016-05-18 07:45:54
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.

(Re: Min_25)
No other test cases are provided.
Please check your code carefully.

Got a stupid int^3 does not fit in a long bug. Fixed and got AC now.

Last edit: 2014-10-14 02:01:07
wisfaq: 2014-10-19 11:09:53

probably something like the following would cure precision issues:
function icbrt(x):
res=int(cbrt(x))
while res*res*res<x:res+=1
if res*res*res>x:res-=1
return res

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()...

@Min_25: Thanks for clarifying. It's a little surprising but not that much, since we are taking the floor of a value that is very close to an integer. (Adding 1e-9 before casting makes it output 13.)

---(Re: Min_25)---
@Mitch
Yes, I think so, too. Floating functions have basically some errors.

Last edit: 2014-07-03 16:12:54
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)).

(Re: Min_25)
Your WA was caused by a precision issue of cbrt.
For example, (long long)cbrt(13^3) returns 12.
(This result seems to be compiler-dependent.)

Yes, theoretically $S_2(n)$ can be calculated in $O(n^{5/9})$,
but $O(n^{2/3})$ solutions run faster than it unless $n$ is sufficiently large.

@Min_25: seems it doesn't work neither with
#define cubert(x) (exp(log(x)/3))
nor
cbrtf(n)
nor
pow(n, 1.0/3.0).
My gcc 4.3.4 on 64-bit Linux gives (long long)cbrt(13*13*13) == 13

So, anyway, the problem is beautiful! Reminds me of that PE beauty which I miss so.

FINALLY!
Nothing can be more idiotic than fighting against compiler when you know you're right.
cbrt() in spoj gcc 4.3.2 is completely broken.
Tried several ways to compute cubic root. It seems any method required any function from math.h doesn't work. Halley's integer algorithm gave TLE. Then found very elegant algoirthm for n-th root using no math.h. And here we are!
NB. My fear of floats, doubles and all that math.h-like things is increasing in geometric progression... In int we trust.

Thank you, Min_25!

---(Re: Min_25)---
@wellwet
Congratulations! Thank you !
(Your Halley's integer algorithm has a overflow issue.)

@Mitch
cbrt(13 * 13 * 13); returns 13,
but int n; scanf("%d", &n); cbrt(n * n * n); (input: 13) returns 12.

http://ideone.com/NcuR4P

Last edit: 2014-07-03 15:22:16
RIVU DAS: 2014-10-19 11:09:53

@Min_25 - What is your complexity??

(Re: Min_25) About O(n^(2/3)).

Last edit: 2014-07-02 22:47:51

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