Dado un número entero N , la tarea es encontrar la suma del Máximo Común Divisor de todos los números hasta N con N mismo.
Ejemplos:
Entrada: N = 12
Salida: 40
Explicación:
GCD de [1, 12] = 1, [2, 12] = 2, [3, 12] = 3, [4, 12] = 4, [5, 12] = 1, [6, 12] = 6, [7, 12] = 1, [8, 12] = 4, [9, 12] = 3, [10, 12] = 2, [11, 12] = 1, [12, 12] = 12. La suma es (1 + 2 + 3 + 4 + 1 + 6 + 1 + 4 + 3 + 2 + 1 + 12) = 40.
Entrada: N = 2
Salida: 3
Explicación:
GCD de [1, 2] = 1, [2, 2] = 2 y su suma es 3.
Enfoque ingenuo: una solución simple es iterar sobre todos los números del 1 al N y encontrar su mcd con el mismo N y seguir añadiéndolos.
Complejidad de tiempo: O(N * log N)
Enfoque eficiente:
Para optimizar el enfoque mencionado anteriormente, debemos observar que GCD(i, N) da uno de los divisores de N . Entonces, en lugar de ejecutar un ciclo de 1 a N, podemos verificar para cada divisor de N cuántos números hay con GCD (i, N) igual que ese divisor.
Ilustración:
Por ejemplo N = 12, sus divisores son 1, 2, 3, 4, 6, 12.
Números en el rango [1, 12] cuyo MCD con 12 es:
- 1 son {1, 5, 7, 11}
- 2 son {2, 10}
- 3 son {3, 9}
- 4 son {4, 8}
- 6 es {6}
- 12 es {12}
Entonces la respuesta es; 1*4 + 2*2 + 3*2 + 4*2 + 6*1 + 12*1 = 40.
- Entonces tenemos que encontrar el número de enteros de 1 a N con MCD d , donde d es un divisor de N . Consideremos x 1 , x 2 , x 3 , …. x n como los diferentes enteros de 1 a N tales que su MCD con N es d.
- Como MCD(x i , N) = d entonces MCD(x i /d, N/d) = 1
- Entonces, el conteo de enteros de 1 a N cuyo MCD con N es d es la Función de Euler Totient de (N/d) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the Sum
// of GCD of all integers up to N
// with N itself
#include <bits/stdc++.h>
using namespace std;
// Function to Find Sum of
// GCD of each numbers
int getCount(int d, int n)
{
int no = n / d;
int result = no;
// Consider all prime factors
// of no. and subtract their
// multiples from result
for (int p = 2; p * p <= no; ++p) {
// Check if p is a prime factor
if (no % p == 0) {
// If yes, then update no
// and result
while (no % p == 0)
no /= p;
result -= result / p;
}
}
// If no has a prime factor greater
// than sqrt(n) then at-most one such
// prime factor exists
if (no > 1)
result -= result / no;
// Return the result
return result;
}
// Finding GCD of pairs
int sumOfGCDofPairs(int n)
{
int res = 0;
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
// Calculate the divisors
int d1 = i;
int d2 = n / i;
// Return count of numbers
// from 1 to N with GCD d with N
res += d1 * getCount(d1, n);
// Check if d1 and d2 are
// equal then skip this
if (d1 != d2)
res += d2 * getCount(d2, n);
}
}
return res;
}
// Driver code
int main()
{
int n = 12;
cout << sumOfGCDofPairs(n);
return 0;
}
Java
// Java program to find the Sum
// of GCD of all integers up to N
// with N itself
class GFG{
// Function to Find Sum of
// GCD of each numbers
static int getCount(int d, int n)
{
int no = n / d;
int result = no;
// Consider all prime factors
// of no. and subtract their
// multiples from result
for(int p = 2; p * p <= no; ++p)
{
// Check if p is a prime factor
if (no % p == 0)
{
// If yes, then update no
// and result
while (no % p == 0)
no /= p;
result -= result / p;
}
}
// If no has a prime factor greater
// than Math.sqrt(n) then at-most one such
// prime factor exists
if (no > 1)
result -= result / no;
// Return the result
return result;
}
// Finding GCD of pairs
static int sumOfGCDofPairs(int n)
{
int res = 0;
for(int i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
// Calculate the divisors
int d1 = i;
int d2 = n / i;
// Return count of numbers
// from 1 to N with GCD d with N
res += d1 * getCount(d1, n);
// Check if d1 and d2 are
// equal then skip this
if (d1 != d2)
res += d2 * getCount(d2, n);
}
}
return res;
}
// Driver code
public static void main(String[] args)
{
int n = 12;
System.out.print(sumOfGCDofPairs(n));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to find the sum # of GCD of all integers up to N # with N itself # Function to Find Sum of # GCD of each numbers def getCount(d, n): no = n // d; result = no; # Consider all prime factors # of no. and subtract their # multiples from result for p in range(2, int(pow(no, 1 / 2)) + 1): # Check if p is a prime factor if (no % p == 0): # If yes, then update no # and result while (no % p == 0): no //= p; result -= result // p; # If no has a prime factor greater # than Math.sqrt(n) then at-most one such # prime factor exists if (no > 1): result -= result // no; # Return the result return result; # Finding GCD of pairs def sumOfGCDofPairs(n): res = 0; for i in range(1, int(pow(n, 1 / 2)) + 1): if (n % i == 0): # Calculate the divisors d1 = i; d2 = n // i; # Return count of numbers # from 1 to N with GCD d with N res += d1 * getCount(d1, n); # Check if d1 and d2 are # equal then skip this if (d1 != d2): res += d2 * getCount(d2, n); return res; # Driver code if __name__ == '__main__': n = 12; print(sumOfGCDofPairs(n)); # This code is contributed by Amit Katiyar
C#
// C# program to find the sum
// of GCD of all integers up to N
// with N itself
using System;
class GFG{
// Function to find sum of
// GCD of each numbers
static int getCount(int d, int n)
{
int no = n / d;
int result = no;
// Consider all prime factors
// of no. and subtract their
// multiples from result
for(int p = 2; p * p <= no; ++p)
{
// Check if p is a prime factor
if (no % p == 0)
{
// If yes, then update no
// and result
while (no % p == 0)
no /= p;
result -= result / p;
}
}
// If no has a prime factor greater
// than Math.Sqrt(n) then at-most
// one such prime factor exists
if (no > 1)
result -= result / no;
// Return the result
return result;
}
// Finding GCD of pairs
static int sumOfGCDofPairs(int n)
{
int res = 0;
for(int i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
// Calculate the divisors
int d1 = i;
int d2 = n / i;
// Return count of numbers
// from 1 to N with GCD d with N
res += d1 * getCount(d1, n);
// Check if d1 and d2 are
// equal then skip this
if (d1 != d2)
res += d2 * getCount(d2, n);
}
}
return res;
}
// Driver code
public static void Main(String[] args)
{
int n = 12;
Console.Write(sumOfGCDofPairs(n));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript Program to find the Sum
// of GCD of all integers up to N
// with N itself
// Function to Find Sum of
// GCD of each numbers
function getCount(d, n)
{
let no = Math.floor(n / d);
let result = no;
// Consider all prime factors
// of no. and subtract their
// multiples from result
for (let p = 2; p * p <= no; ++p) {
// Check if p is a prime factor
if (no % p == 0) {
// If yes, then update no
// and result
while (no % p == 0)
no = Math.floor(no / p);
result = Math.floor(result - result / p);
}
}
// If no has a prime factor greater
// than sqrt(n) then at-most one such
// prime factor exists
if (no > 1)
result = Math.floor(result - result / no);
// Return the result
return result;
}
// Finding GCD of pairs
function sumOfGCDofPairs(n)
{
let res = 0;
for (let i = 1; i * i <= n; i++) {
if (n % i == 0) {
// Calculate the divisors
let d1 = i;
let d2 = Math.floor(n / i);
// Return count of numbers
// from 1 to N with GCD d with N
res += d1 * getCount(d1, n);
// Check if d1 and d2 are
// equal then skip this
if (d1 != d2)
res += d2 * getCount(d2, n);
}
}
return res;
}
// Driver code
let n = 12;
document.write(sumOfGCDofPairs(n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
40
Complejidad de tiempo: O(N)