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.
hide comments
|
spojmehedi:
2019-10-07 22:32:50
Be carefull about Overflow..10 WA..Finally AC
|
|
noble_mushtak:
2019-07-06 18:07:13
This is actually a rather straightforward problem, in my opinion. Solved in two tries (first try, I forgot to put a small line of code). 9.32 seconds and 248 MB in C++14. However, factoring in O(sqrt(n)) is not necessarily fast enough. I was able to handle each query in O(π(sqrt(n))=O(sqrt(n)/log(n)). Last edit: 2019-07-06 18:45:23 |
|
maximum_01:
2019-07-02 12:00:46
factorizing in o(root(n)) but still getting tle
|
|
frochbg:
2019-05-31 16:16:01
Nice problem with fast factorization :) |
|
scolar_fuad:
2019-04-13 16:00:05
please share idea is any ??
|
|
des1997:
2018-06-23 11:50:33
ran in 3.02 seconds:) |
|
karthik1997:
2017-12-28 13:39:05
Can't go below 2s . :( |
|
kmkhan_014:
2017-12-21 16:55:26
this is extremel !!! AC in 15s |
|
mastik5h_1998:
2017-06-23 07:40:49
very annoying question.......
|
|
oualiamine:
2017-03-20 22:12:50
what does 1e16 means?
|
| 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 |
RSS