You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFLCM - Editorial

PROBLEM LINK:

Practice
Contest

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:

  1. We should check that p is not equal to N / p while adding N / p.
  2. 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

This question is marked "community wiki".

asked 11 Apr '15, 14:59

adurysk's gravatar image

4★adurysk ♦
92831928
accept rate: 11%

edited 01 Jun '16, 20:22

admin's gravatar image

0★admin ♦♦
15.5k347484505


@ikagotso I think there is a precision issue was with division in every step as of iteration in the formula as the division is not integral. I made slight change to your code and it got accepted. Check out the submission here

link

answered 14 Apr '15, 16:49

abhra73's gravatar image

3★abhra73
111
accept rate: 0%

Can please anyone point out my fault. My code ( http://www.codechef.com/viewsolution/6630393 ) seems quite the same to the one given above.

link

answered 13 Apr '15, 18:06

debverine's gravatar image

2★debverine
112
accept rate: 0%

@debverine instead of 'int' if you used 'long' then its easily passes all test cases

(13 Apr '15, 20:01) viperx4★

thank you @viperx . I made a terrible mistake :(

(14 Apr '15, 00:38) debverine2★

Awesome editorial !!shook me to core

link

answered 13 Apr '15, 18:36

ujjwal94's gravatar image

2★ujjwal94
1
accept rate: 0%

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

link

answered 15 Apr '15, 15:16

krishna_keshav's gravatar image

3★krishna_keshav
1112
accept rate: 0%

Answer is hidden as author is suspended. Click here to view.

answered 02 May '15, 12:07

bangga's gravatar image

0★bangga
(suspended)
accept rate: 0%

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.

link

answered 24 Jun '15, 18:00

dhavalmehta's gravatar image

4★dhavalmehta
563
accept rate: 30%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,354
×752
×184
×74
×9

question asked: 11 Apr '15, 14:59

question was seen: 4,631 times

last updated: 24 Jun '16, 23:43