PROBLEM LINK:Author: Abhra Dasgupta DIFFICULTY:SIMPLE PREREQUISITES:LCM PROBLEM:For a given positive integer N, what is the maximum sum of distinct numbers such that the Least Common Multiple of all these numbers is N. EXPLANATION:As N is LCM of all the numbers, all of them will be divisors of N. As each divisor can occur only once, the answer will be sum of all the divisors of N. Subtask 1 As N <= 10^5, we can iterate through each i from 1 to N and add all divisors. Complexity is O(N) per test case. Subtask 2 We can observe that for each pair of divisors (p, q), such that p * q = N, either p <= sqrt(N) or q <= sqrt(N), else p * q will be greater than N. Also we can check that for each divisor p, there exists a distinct q such that p * q = N. Without loss of generality let us assume p <= q. We can iterate for each p from 1 to sqrt(N) and if p is a divisor of N, then add both p and N / p to the answer. Complexity is O(sqrt(N)) per test case. C++ Code
Common Mistakes:
AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 11 Apr '15, 14:59

Can please anyone point out my fault. My code ( http://www.codechef.com/viewsolution/6630393 ) seems quite the same to the one given above. answered 13 Apr '15, 18:06
@debverine instead of 'int' if you used 'long' then its easily passes all test cases
(13 Apr '15, 20:01)
thank you @viperx . I made a terrible mistake :(
(14 Apr '15, 00:38)

Though this is a very simple approach,but still i want a clearification on it.**partially correct**.It shows TLE for higher subtask. answered 15 Apr '15, 15:16

Answer is hidden as author is suspended. Click here to view.
answered 02 May '15, 12:07

my solution http://www.codechef.com/viewsolution/7277789 is accepted. I used same logic but i got WA on http://www.codechef.com/viewsolution/7277717 please anyone tell me why it was gave Wrong ans ? Thanks in advance. answered 24 Jun '15, 18:00
