SPOJ LCMSUM – LCM Sum

Problem

Problem Link – SPOJ LCMSUM

Given $n$, calculate the sum $LCM(1,n) + LCM(2,n) + … + LCM(n,n)$, where $LCM(i,n)$ denotes the Least Common Multiple of the integers $i$ and $n$.

Solution

I recently solved this problem and found the solution really interesting. You can find the formula that solves this problem on OEIS. I will show you the derivation here.

In order to solve this problem, you need to know about Euler Phi Function, finding Divisor using Sieve and some properties of LCM and GCD.

Define SUM

Let us define a variable SUM which we need to find.

$SUM = LCM(1,n) + LCM(2,n) + … + LCM(n,n)$ (take $LCM(n,n)$ to the other side for now )
$SUM – LCM(n,n) = LCM(1,n) + LCM(2,n) + … + LCM(n-1,n)$

We know that $LCM(n,n) = n$.

$SUM – n = LCM(1,n) + LCM(2,n) + … + LCM(n-1,n)$ ($eq 1$)

Reverse and Add

$SUM – n = LCM(1,n) + LCM(2,n) + … + LCM(n-1,n)$ (Reverse $eq 1$ to get $eq 2$)
$SUM – n = LCM(n-1,n) + LCM(n-2,n) + … + LCM(1,n)$ ( $eq 2$ )

No what will we get if we add $eq 1$ with $eq 2$? Well, we need to do more work to find that.

Sum of $LCM(a,n) + LCM(n-a,n)$

$x = LCM(a,n) + LCM(n-a,n)$
$x = \frac{an}{gcd(a,n)} + \frac{(n-a)n}{gcd(n-a,n)}$ ($eq 3$)

Arghh. Now we need to prove that $gcd(a,n)$ is equal to $gcd(n-a,n)$.

If $c$ divides $a$ and $b$, then, $c$ will divide $a+b$ and $a-b$. This is common property of division. So, if $g = gcd(a,n)$ divides $a$ and $n$, then it will also divide $n-a$. Hence, $gcd(a,n)=gcd(n-a,n)$.

So $eq 3$ becomes:

$x = \frac{an}{gcd(a,n)} + \frac{(n-a)n}{gcd(a,n)}$
$x = \frac{an + n^2 -an}{gcd(a,n)}$.
$x = \frac{n^2}{gcd(a,n)}$.

Now, we can continue adding $eq 1$ with $eq 2$.

Reverse and Add Continued

$SUM – n = LCM(1,n) + LCM(2,n) + … + LCM(n-1,n)$ ($eq 1$)
$SUM – n = LCM(n-1,n) + LCM(n-2,n) + … + LCM(1,n)$ ( $eq 2$ Add them )$2(SUM-n)= \frac{n^2}{gcd(1,n)} + \frac{n^2}{gcd(2,n)} + … \frac{n^2}{gcd(n-1,n)}$
$2(SUM-n ) = \sum_{i=1}^{n-1}\frac{n^2}{gcd(i,n)}$
$2(SUM-n ) = n\sum_{i=1}^{n-1}\frac{n}{gcd(i,n)}$ ( take $n$ common )

Group Similar GCD

What are the possible values of $g = gcd(i,n)$? Since $g$ must divide $n$, $g$ needs to be a divisor of $n$. So we can list the possible values of $gcd(i,n)$ by finding the divisors of $n$.

Let $Z = n\sum_{i=1}^{n-1}\frac{n}{gcd(i,n)}$. Now, every time $gcd(i,n) = d$, where $d$ is a divisior of $n$, $n \times \frac{n}{d}$ is added to $Z$. Therefore, we just need to find, for each divisor $d$, how many times $n \times \frac{n}{d}$ is added to $Z$.

How many values $i$ can we put such that $gcd(i,n) = d$? There are $\phi(\frac{n}{d})$ possible values of $i$ for which we get $gcd(i,n)=d$. Therefore:

$2(SUM-n ) = n\sum_{i=1}^{n-1}\frac{n}{gcd(i,n)}$
$2(SUM-n ) = n\sum_{d |n, d \neq n } \phi(\frac{n}{d}) \times \frac{n}{d}$ (but, $\frac{n}{d}$ is also a divisor of $n$ )
$2(SUM-n ) = n\sum_{d |n, d \neq 1 } \phi(d) \times d$ ( when $d = 1$, we get $\phi(1)times 1$ )
$2(SUM-n ) = n( \sum_{d |n } ( \phi(d) \times d ) -1 )$
$2(SUM-n ) = n \sum_{d |n } (\phi(d) \times d ) – n$
$2SUM – 2n + n = n\sum_{d |n } \phi(d) \times d$
$2SUM – n = n\sum_{d |n } \phi(d) \times d$

$$2SUM = n( \sum_{d |n } \phi(d) \times d )+ n \\
2SUM = n ( \sum_{d |n } ( \phi(d) \times d ) + 1 ) \\
\therefore SUM = \frac{n}{2} ( \sum_{d |n } ( \phi(d) \times d ) + 1 )$$

Using this formula we can solve the problem.

Code


#include <bits/stdc++.h>

#define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)

using namespace std;
typedef long long vlong;

vlong res[1000010];
vlong phi[1000010];

void precal( int n ) {
    // Calculate phi from 1 to n using sieve
    FOR(i,1,n) phi[i] = i;
    FOR(i,2,n) {
        if ( phi[i] == i ) {
        for ( int j = i; j <= n; j += i ) {
            phi[j] /= i;
            phi[j] *= i - 1;
        }
    }
 }

 // Calculate partial result using sieve
 // For each divisor d of n, add phi(d)*d to result array
 FOR(i,1,n){
    for ( int j = i; j <= n; j += i ) {
        res[j] += ( i * phi[i] );
    }
 }
}

int main () {
    precal( 1000000 );

    int kase;
    scanf ( "%d", &kase );

    while ( kase-- ) {
        vlong n;
        scanf ( "%lld", &n );

        // We already have partial result in res[n]
        vlong ans = res[n] + 1;
        ans *= n;
        ans /= 2;

        printf ( "%lld\n", ans );
    }

    return 0;
}

We need to precalculate partial result using a sieve for all values of $N$. Precalculation has a complexity of $O(N \ ln(N))$. After pre-calculation, for each $N$ we can answer in $O(1)$.

Reference

  1. OEIS - A051193