Thursday, August 27, 2015

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 nee to precalculate partial result using a sieve for all values of $N$. Precalculation has a complexity of $O(N\: lnN)$. After pre-calculation, for each $N$ we can answer in $O(1)$.

Reference

  1. OEIS - A051193

8 comments:

  1. Can you please explain how did you calculated phi() ?

    ReplyDelete
    Replies
    1. I used Sieve to generate all phi() in O(N). First initiate phi[x] = x for all values from 1 to N. Then, take a prime p, and multiply (p-1)/p to all multiples of p between 1 and N. This way, you will be left with phi value at the end.

      Delete
    2. @Mohammad samiul islam can you please elaborate why do you multiple it and first take division and then multiplication .

      Delete
    3. @Shubham: Are you talking about line 17 and 18? If I multiply first and then divide, then there is a possibility that phi[j] will overflow. Dividing first and then multiplying reduces risk of overflow.

      Delete

Leave comments for Queries, Bugs and Hugs.