Dado un entero n , la tarea es encontrar la suma:
MCM(1, n) + MCM(2, n) + MCM(3, n) + … + MCM(n, n)
donde MCM(i, n) es el Mínimo Común Múltiplo de i y n.
Ejemplos:
Entrada: 3
Salida: 10
MCM(1, 3) + MCM(2, 3) + MCM(3, 3) = 3 + 6 + 3 = 12Entrada: 5
Salida: 55
MCM(1, 5) + MCM(2, 5) + MCM(3, 5) + MCM(4, 5) + MCM(5, 5) = 55
Enfoque ingenuo: MCM de dos números a y b = (a * b) / mcd(a, b) donde mcd(a, b) es el máximo común divisor de a y b .
- Calcule los valores de LCM individuales para todos los pares a partir de (1, n) a (n, n) .
- Sume todos los resultados de LCM del paso anterior.
- Imprime la suma al final.
A continuación se muestra la implementación del enfoque anterior:
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 i.e. (i * n) / gcd(i, n)
long long int lcm = (i * n) / gcd;
// Update sum
sum = sum + lcm;
}
return sum;
}
// Driver code
int main()
{
int n = 3;
cout << lcmSum(n);
return 0;
}
Java
// 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 i.e. (i * n) / gcd(i, n)
int lcm = (i * n) / gcd;
// Update sum
sum = sum + lcm;
}
return sum;
}
// 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 i.e. (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 i.e. (i * n) / gcd(i, n)
int lcm = (i * n) / gcd;
// Update sum
sum = sum + lcm;
}
return sum;
}
// 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 i.e. (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 i.e. (i * n) / gcd(i, n)
var lcm = (i * n) / _gcd;
// Update sum
sum = sum + lcm;
}
return sum;
}
// Driver code
var n = 3;
document.write(lcmSum(n));
// This code is contributed by Ankita saini
</script>
Producción:
12
Complejidad de tiempo: O(n * logn), donde n representa el entero dado.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Enfoque eficiente: utilizando la función de tociente de Euler ,
∑LCM(i, n) = ((∑(d * ETF(d)) + 1) * n) / 2
donde ETF(d) es la función de tociente de Euler de d y d pertenece el conjunto de divisores de n .
Ejemplo:
Sea n 5 entonces MCM(1, 5) + MCM(2, 5) + MCM(3, 5) + MCM(4, 5) + MCM(5, 5)
= 5 + 10 + 15 + 20 + 5
= 55
Con la función Euler Totient:
Todos los divisores de 5 son {1, 5}
Por lo tanto, ((1*ETF(1) + 5*ETF(5) + 1) * 5) / 2 = 55
A continuación se muestra la implementación del enfoque anterior:
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
// 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));
}
}
// This code is contributed by chandan_jnu
PHP
<?php
// PHP implementation of the approach
$n = 10002;
$phi = array_fill(0, $n + 2, 0);
$ans = array_fill(0, $n + 2, 0);
// Euler totient Function
function ETF()
{
global $phi, $n;
for ($i = 1; $i <= $n; $i++)
{
$phi[$i] = $i;
}
for ($i = 2; $i <= $n; $i++)
{
if ($phi[$i] == $i)
{
$phi[$i] = $i - 1;
for ($j = 2 * $i; $j <= $n; $j += $i)
{
$phi[$j] = (int)(($phi[$j] *
($i - 1)) / $i);
}
}
}
}
// Function to return the required LCM sum
function LcmSum($m)
{
ETF();
global $ans, $n, $phi;
for ($i = 1; $i <= $n; $i++)
{
// Summation of d * ETF(d) where
// d belongs to set of divisors of n
for ($j = $i; $j <= $n; $j += $i)
{
$ans[$j] += ($i * $phi[$i]);
}
}
$answer = $ans[$m];
$answer = ($answer + 1) * $m;
$answer = (int)($answer / 2);
return $answer;
}
// Driver code
$m = 5;
echo LcmSum($m);
// This code is contributed by chandan_jnu
?>
Javascript
<script>
// javascript implementation of the approach
var n = 1000002;
var phi = Array(n + 2).fill(0);
var ans = Array(n + 2).fill(0);
// Euler totient Function
function ETF() {
for (i = 1; i <= n; i++) {
phi[i] = i;
}
for (i = 2; i <= n; i++) {
if (phi[i] == i) {
phi[i] = i - 1;
for (j = 2 * i; j <= n; j += i) {
phi[j] = (phi[j] * (i - 1)) / i;
}
}
}
}
// Function to return the required LCM sum
function LcmSum(m) {
ETF();
for (i = 1; i <= n; i++) {
// Summation of d * ETF(d) where
// d belongs to set of divisors of n
for (j = i; j <= n; j += i) {
ans[j] += (i * phi[i]);
}
}
var answer = ans[m];
answer = (answer + 1) * m;
answer = answer / 2;
return answer;
}
// Driver code
var m = 5;
document.write(LcmSum(m));
// This code is contributed by aashish1995
</script>
Producción:
55
Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Mostafijur Rahaman y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA