Suma de GCD de todos los números hasta N con N mismo

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:
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)
 

Publicación traducida automáticamente

Artículo escrito por yash2040 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *