UDIVSUM - The Sum of Unitary Divisors
A natural number $d$ is a unitary divisor of $n$ if $d$ is a divisor of $n$ and if $d$ and $\frac{n}{d}$ are coprime.
Let $\sigma^{*}(n)$ be the sum of the unitary divisors of $n$. For example, $\sigma^{*}(1) = 1$, $\sigma^{*}(2) = 3$ and $\sigma^{*}(6) = 12$.
Let $$S(n) = \sum_{i=1}^n \sigma^{*}(i).$$
Given $n$, find $S(n) \bmod 2^{64}$.
Input
There are multiple test cases. The first line of input contains an integer $T$ ($1 \le T \le 50000$), indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 5 \times 10^{13}$).
Output
For each test case, output a single line containing $S(n) \bmod 2^{64}$.
Example
Input:
7 1 2 3 4 5 100 100000
Output:
1 4 8 13 19 6889 6842185909
Information
There are 8 Input files.
- Input #1: $1 \le n \le 50000$, TL=1s
- Input #2: $1 \le T \le 1000, \ 1 \le n \le 5 \times 10^7$, TL=5s
- Input #3: $1 \le T \le 300, \ 1 \le n \le 5 \times 10^8$, TL=5s
- Input #4: $1 \le T \le 80, \ 1 \le n \le 5 \times 10^9$, TL=5s
- Input #5: $1 \le T \le 30, \ 1 \le n \le 5 \times 10^{10}$, TL=10s
- Input #6: $1 \le T \le 10, \ 1 \le n \le 5 \times 10^{11}$, TL=10s
- Input #7: $1 \le T \le 3, \ 1 \le n \le 5 \times 10^{12}$, TL=10s
- Input #8: $T=1, \ 1 \le n \le 5 \times 10^{13}$, TL=10s
My unoptimized C++ solution runs in 8.9 sec (total time). And with some constant optimization, now my C++ solution runs in 1.03 sec (total time).
hide comments
zimpha:
2018-01-18 17:28:55
@[Rampage] Blue.Mary, I don't think so. It just replaces uint64_t with uint128_t, and it's better to focus more on the method. |
|
[Rampage] Blue.Mary:
2018-01-18 11:14:50
It's more interesting if the problem doesn't require the answer to modulo 2^64 :P |
Added by: | zimpha |
Date: | 2018-01-17 |
Time limit: | 1s-10s |
Source limit: | 10240B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |