Сумма НОК (1, n), НОК (2, n), НОК (3, n),…, НОК (n, n)

Опубликовано: 5 Января, 2022

Для целого числа n нужно найти сумму:

LCM(1, n) + LCM(2, n) + LCM(3, n) + … + LCM(n, n)
where LCM(i, n) is the Least Common Multiple of i and n.

Примеры:

Input: 3
Output: 10
LCM(1, 3) + LCM(2, 3) + LCM(3, 3) = 3 + 6 + 3 = 12
Input: 5
Output: 55
LCM(1, 5) + LCM(2, 5) + LCM(3, 5) + LCM(4, 5) + LCM(5, 5) = 55

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: НОК двух чисел a и b = (a * b) / gcd (a, b), где gcd (a, b) - наибольший общий делитель чисел a и b .

Вычислите значения индивидуального НОК для всех пар, начиная с (1, n) и заканчивая (n, n) .
Просуммируйте все результаты НОК из предыдущего шага.
В конце выведите сумму.

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ implementation of the approach
 #include <bits/stdc++.h>
 using namespace std;
 #define ll long long int
 // Function to calculate the required LCM sum
 ll lcmSum( long long n)
 {
    ll sum = 0;
    for ( long long int i = 1; i <= n; i++) { 
        // GCD of i and n
        long long int gcd = __gcd(i, n); 
        // LCM of i and n ie (i * n) / gcd(i, n)
        long long int lcm = (i * n) / gcd; 
        // Update sum
        sum = sum + lcm;
    }
    sum; return
 }
 // Driver code
 int main()
 {
    int n = 3; 
    cout << lcmSum(n);
    return 0;
 }

Джава

 // Java implementation of the approach
 import java.util.*;
 class GFG
 {
 // return gcd of two numbers
 static int gcd( int a, int b)
 {
    // Everything divides 0
    if (a == 0 )
        return b;
    if (b == 0 )
        return a;
    
    // base case
    if (a == b)
        return a;
    
    // a is greater
    if (a > b)
        return gcd(a - b, b);
    return gcd(a, b - a);
 }
 // Function to calculate the required LCM sum
 static int lcmSum( int n)
 {
    int sum = 0 ; 
    for ( int i = 1 ; i <= n; i++)
    {
        // GCD of i and n
        int gcd = gcd(i, n); 
        // LCM of i and n ie (i * n) / gcd(i, n)
        int lcm = (i * n) / gcd; 
        // Update sum
        sum = sum + lcm;
    }
    sum; return
 }
 // Driver code
 public static void main(String args[])
 {
    int n = 3 ; 
    System.out.println(lcmSum(n));
 }
 }
 // This code is contributed by
 // Surendra _Gangwar

Python3

 # Python3 implementation of the approach
 import math
 # Function to calculate the required LCM sum
 def lcmSum(n): 
    Sum = 0
    for i in range ( 1 , n + 1 ): 
        # GCD of i and n
        gcd = math.gcd(i, n) 
        # LCM of i and n ie (i * n) / gcd(i, n)
        lcm = (i * n) / / gcd 
        # Update sum
        Sum = Sum + lcm 
    return Sum
 # Driver code
 if __name__ = = "__main__" : 
    n = 3
    print (lcmSum(n))
 # This code is contributed by Rituraj Jain

C #

 // C# implementation of the approach
 class GFG
 {
 // return gcd of two numbers
 static int gcd1( int a, int b)
 {
    // Everything divides 0
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    
    // base case
    if (a == b)
        return a;
    
    // a is greater
    if (a > b)
        return gcd1(a - b, b);
    return gcd1(a, b - a);
 }
 // Function to calculate the required LCM sum
 static int lcmSum( int n)
 {
    int sum = 0; 
    for ( int i = 1; i <= n; i++)
    {
        // GCD of i and n
        int gcd = gcd1(i, n); 
        // LCM of i and n ie (i * n) / gcd(i, n)
        int lcm = (i * n) / gcd; 
        // Update sum
        sum = sum + lcm;
    }
    sum; return
 }
 // Driver code
 static void Main()
 {
    int n = 3; 
    System.Console.WriteLine(lcmSum(n));
 }
 }
 // This code is contributed by chandan_jnu

PHP

 <?php
 // PHP implementation of the approach
 function __gcd( $a , $b )
 {
    if ( $b == 0)
    return $a ;
    return __gcd( $b , $a % $b );
 }
 // Function to calculate the required LCM sum
 function lcmSum( $n )
 {
    $sum = 0; 
    for ( $i = 1; $i <= $n ; $i ++)
    {
        // GCD of i and n
        $gcd = __gcd( $i , $n ); 
        // LCM of i and n ie (i * n) / gcd(i, n)
        $lcm = ( $i * $n ) / $gcd ; 
        // Update sum
        $sum = $sum + $lcm ;
    }
    return $sum ;
 }
 // Driver code
 $n = 3;
 echo lcmSum( $n );
 // This code is contributed by chandan_jnu
 ?>

Javascript

 <script>
 // Javascript implementation of the approach
 // return gcd of two numbers
 function gcd(a, b)
 {
    
    // Everything divides 0
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    
    // base case
    if (a == b)
        return a;
    
    // a is greater
    if (a > b)
        return gcd(a - b, b);
        
    return gcd(a, b - a);
 }
 // Function to calculate the required LCM sum
 function lcmSum(n)
 {
    var sum = 0; 
    for ( var i = 1; i <= n; i++)
    {
        // GCD of i and n
        var _gcd = gcd(i, n); 
        // LCM of i and n ie (i * n) / gcd(i, n)
        var lcm = (i * n) / _gcd; 
        // Update sum
        sum = sum + lcm;
    }
    sum; return
 }
 // Driver code
 var n = 3;
 document.write(lcmSum(n));
    
// This code is contributed by Ankita saini
   
</script>

Выход:

Эффективный подход: использование функции Эйлера Totient,
∑LCM (i, n) = ((∑ (d * ETF (d)) + 1) * n) / 2
где ETF (d) - функция Эйлера от d, а d принадлежит множеству делителей n .

Пример:

Let n be 5 then LCM(1, 5) + LCM(2, 5) + LCM(3, 5) + LCM(4, 5) + LCM(5, 5)
= 5 + 10 + 15 + 20 + 5
= 55
With Euler Totient Function:
All divisors of 5 are {1, 5}
Hence, ((1*ETF(1) + 5*ETF(5) + 1) * 5) / 2 = 55

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ implementation of the approach
 #include <bits/stdc++.h>
 using namespace std;
 #define n 1000002
 #define ll long long int
 ll phi[n + 2], ans[n + 2];
 // Euler totient Function
 void ETF()
 {
    for ( int i = 1; i <= n; i++) {
        phi[i] = i;
    }
    for ( int i = 2; i <= n; i++) {
        if (phi[i] == i) {
            phi[i] = i - 1;
            for ( int j = 2 * i; j <= n; j += i) {
                phi[j] = (phi[j] * (i - 1)) / i;
            }
        }
    }
 }
 // Function to return the required LCM sum
 ll LcmSum( int m)
 {
    ETF();
    for ( int i = 1; i <= n; i++) { 
        // Summation of d * ETF(d) where
        // d belongs to set of divisors of n
        for ( int j = i; j <= n; j += i) {
            ans[j] += (i * phi[i]);
        }
    }
    ll answer = ans[m];
    answer = (answer + 1) * m;
    answer = answer / 2;
    return answer;
 }
 // Driver code
 int main()
 {
    int m = 5; 
    cout << LcmSum(m);
    return 0;
 }

Джава

 // Java implementation of the approach
 class GFG
 {
    
static int n = 1000002 ;
 static int [] phi = new int [n + 2 ];
 static int [] ans = new int [n + 2 ];
 // Euler totient Function
 static void ETF()
 {
    for ( int i = 1 ; i <= n; i++)
    {
        phi[i] = i;
    }
    for ( int i = 2 ; i <= n; i++)
    {
        if (phi[i] == i)
        {
            phi[i] = i - 1 ;
            for ( int j = 2 * i; j <= n; j += i)
            {
                phi[j] = (phi[j] * (i - 1 )) / i;
            }
        }
    }
 }
 // Function to return the required LCM sum
 static int LcmSum( int m)
 {
    ETF();
    for ( int i = 1 ; i <= n; i++)
    {
        // Summation of d * ETF(d) where
        // d belongs to set of divisors of n
        for ( int j = i; j <= n; j += i)
        {
            ans[j] += (i * phi[i]);
        }
    }
    int answer = ans[m];
    answer = (answer + 1 ) * m;
    answer = answer / 2 ;
    return answer;
 }
 // Driver code
 public static void main (String[] args)
 {
    int m = 5 ;
    System.out.println(LcmSum(m));
 }
 }
 // This code is contributed by chandan_jnu

Python3

 # Python3 implementation of the approach
 n = 100002 ;
 phi = [ 0 ] * (n + 2 );
 ans = [ 0 ] * (n + 2 );
 # Euler totient Function
 def ETF(): 
    for i in range ( 1 , n + 1 ):
        phi[i] = i; 
    for i in range ( 2 , n + 1 ):
        if (phi[i] = = i):
            phi[i] = i - 1 ;
            for j in range ( 2 * i, n + 1 , i):
                phi[j] = (phi[j] * (i - 1 )) / / i;
 # Function to return the required LCM sum
 def LcmSum(m):
    ETF();
    for i in range ( 1 , n + 1 ): 
        # Summation of d * ETF(d) where
        # d belongs to set of divisors of n
        for j in range (i, n + 1 , i):
            ans[j] + = (i * phi[i]); 
    answer = ans[m];
    answer = (answer + 1 ) * m;
    answer = answer / / 2 ;
    return answer;
 # Driver code
 m = 5 ;
 print (LcmSum(m));
 # This code is contributed
 # by chandan_jnu

C #

 // C# implementation of the approach
 using System;
 class GFG
 {
 static int n = 1000002;
 static int [] phi = new int [n + 2];
 static int [] ans = new int [n + 2];
 // Euler totient Function
 static void ETF()
 {
    for ( int i = 1; i <= n; i++)
    {
        phi[i] = i;
    }
    for ( int i = 2; i <= n; i++)
    {
        if (phi[i] == i)
        {
            phi[i] = i - 1;
            for ( int j = 2 * i; j <= n; j += i)
            {
                phi[j] = (phi[j] * (i - 1)) / i;
            }
        }
    }
 }
 // Function to return the required LCM sum
 static int LcmSum( int m)
 {
    ETF();
    for ( int i = 1; i <= n; i++)
    {
        // Summation of d * ETF(d) where
        // d belongs to set of divisors of n
        for ( int j = i; j <= n; j += i)
        {
            ans[j] += (i * phi[i]);
        }
    }
    int answer = ans[m];
    answer = (answer + 1) * m;
    answer = answer / 2;
    return answer;
 }
 // Driver code
 static void Main()
 {
    int m = 5;
    Console.WriteLine(LcmSum(m));
 }

                    
                                            Technical Scripter
                                            Алгоритмы
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИКоличество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023