Sum of MSLCM

Revision en2, by BumbleBee, 2018-02-09 18:51:02

Recently I was trying to solve the problem Sum of MSLCM from ACM ICPC Live Archive.

After a little analysis, I found out that the answer is S — 1, where S is the sum of all X such that,

X = A * (int)(N / A) for all A in the range [1, N].

int ans=0
for(int a=1;a<=n;a++){

But my solution won't pass the time limit if I iterate over the range [1, N] as N can be as large as 20000000.

I couldn't find another solution even after several hours of thinking and decided to search for the solution on the internet. While searching for the solution I found the following code.

#include <bits/stdc++.h>
using namespace std;
#define long long long int
int main()
    long n;
    while(cin>> n && n){
        long ans=0,a=1;
            long x=n/a;
            long y=n/x;
        cout<< ans <<endl;
    return 0;

This solution passed the time limit for the given input range and got accepted.

But I still couldn't understand the formula used in this code. The only optimization I see here is that it doesn't iterate over all the numbers in the range [1, N]. But how does that work?

I want a mathematical explanation of this solution.


  Rev. Lang. By When Δ Comment
en2 English BumbleBee 2018-02-09 18:51:02 6
en1 English BumbleBee 2018-02-09 18:06:54 1548 Initial revision (published)