### 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