| Submit | All submissions | Best solutions | Back to list |
DIVSUM2 - Divisor Summation (Hard) |
Given a natural number n (1 <= n <= 1e16), please output the summation of all its proper divisors.
Definition: A proper divisor of a natural number is the divisor that is strictly less than the number.
e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.
Input
An integer stating the number of test cases (equal to 500), and that many lines follow, each containing one integer between 1 and 1e16 inclusive.
Output
One integer each line: the divisor summation of the integer given respectively.
Example
Input: 3 2 10 20 Output: 1 8 22warning: a naive algorithm may not run in time.
| Added by: | Bin Jin |
| Date: | 2007-08-29 |
| Time limit: | 18.17s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: CPP |
| Resource: | own problem |
hide comments
|
||||||
|
2023-08-13 16:12:59
The first thing I noticed is that what if n=1 ? It doesn't have any proper divisors so the sum is equal to 0 ? |
||||||
|
2022-09-05 17:44:57
Just to make it clear, cpp solutions are getting accepted. |
||||||
|
2021-04-27 20:38:47
Look at languages ....? All except: CPP CPP not accepted? Last edit: 2021-04-27 20:39:13 |
||||||
|
2020-10-19 18:30:10
use div_sum = 1LL & bitset for sieve |
||||||
|
2020-07-13 13:26:37
Use bitwise sieve to store the primes up to 10^8 then for each query just use the simple sum of divisors algorithm . it's very straight forward problem just you need to use bitwise sieve instead of general sieve to store primes up to 10^8 |
||||||
|
2020-06-11 18:53:50
is the ans fit in long long |
||||||
|
2020-05-18 20:06:08
check out my code. can't get AC. TLE <snip> Last edit: 2022-09-06 08:32:44 |
||||||
|
2020-03-31 21:54:26
got acc in simple SOD...just range and time limit big.. |
||||||
|
2019-12-07 12:59:38
can it be that the test cases are kinda broken here. I tested the sample inputs and everything worked ?? |
||||||
|
2019-11-30 07:27:49
4.89 seconds and 79 MB :) Did optimized sieve to find out primes, and later did prime factorizing, and some calculation. Handled each query in O(π(sqrt(n))=O(sqrt(n)/log(n)). |
||||||
RSS