PROBLEM LINK:
[Practice][111]
[Contest][222]
Author: Abhra Dasgupta
Tester: Sergey Kulik
Editorialist: Adury Surya Kiran
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
#include<iostream>
using namespace std;
int main(){
int t;
cin>>t;
for(int i = 1; i <= t; i++){
int n, p;
long long sum = 0;
cin >> n;
for(p = 1; p * p <= n; p++){
if(n % p == 0){
sum += p;
if(p != n / p){
sum += n / p;
}
}
}
cout << sum << '\n';
}
return 0;
}
Common Mistakes:
- We should check that p is not equal to N / p while adding N / p.
- The answer can exceed the range of integer in C++, so it should be kept as long long.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution
Tester’s solution
[111]: http://www.codechef.com/problems/CHEFLCM
[222]: http://www.codechef.com/APRIL15/problems/CHEFLCM
