Dado un número N y un número primo P , la tarea es encontrar la suma de los divisores más grandes de cada número en el rango [1, N] , que no es divisible por P .
Ejemplos:
Entrada: N = 8, P = 2
Salida: 22
Explicación: Los números están en el rango [1, 8].
Número Mayor divisor no divisible por P = 2
1 1
2 1
3 3
4 1
5 5
6 3
7 7
8 1
Suma de todos los divisores con la restricción dada = 22.Entrada: N = 10, P = 5
Salida: 43
Explicación: Los números están en el rango [1, 8].
Número Mayor divisor no divisible por P = 5
1 1
2 2
3 3
4 4
5 1
6 6
7 7
8 8
9 9
10 2
Suma de todos los divisores con la restricción dada = 43
Enfoque ingenuo: la idea ingenua es encontrar los divisores para cada número en el rango [1, N] y encontrar los divisores más grandes que no son divisibles por P y esos números. Imprime la suma de todos esos divisores más grandes.
Complejidad temporal: O(N 3/2 )
Espacio auxiliar: O(1)
Enfoque eficiente: La idea es observar que el mayor divisor de un número N no divisible por P sería N mismo si N no es divisible por P . De lo contrario, el divisor requerido será el mismo que el de N/P . A continuación se muestran los pasos:
- Si N no es divisible por P, entonces el divisor más grande será N , súmalo a la suma final.
- Si N es divisible por P, el divisor requerido será el mismo que el de N/P .
- Entonces, encuentra la suma de todos los números que no son divisibles por P y súmales los divisores de aquellos que son divisibles por P por separado.
- La suma total sería N*(N + 1)/2 . Resta la suma de los que son divisibles por P y suma su valor correspondiente llamando recursivamente a la función para encontrar la suma de N/P .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of largest
// divisors of numbers in range 1 to N
// not divisible by prime number P
int func(int N, int P)
{
// Total sum upto N
int sumUptoN = (N * (N + 1) / 2);
int sumOfMultiplesOfP;
// If no multiple of P exist up to N
if (N < P) {
return sumUptoN;
}
// If only P itself is in the range
// from 1 to N
else if ((N / P) == 1) {
return sumUptoN - P + 1;
}
// Sum of those that are divisible by P
sumOfMultiplesOfP
= ((N / P) * (2 * P + (N / P - 1) * P)) / 2;
// Recursively function call to
// find the sum for N/P
return (sumUptoN
+ func(N / P, P)
- sumOfMultiplesOfP);
}
// Driver Code
int main()
{
// Given N and P
int N = 10, P = 5;
// Function Call
cout << func(N, P) << "\n";
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find the sum of largest
// divisors of numbers in range 1 to N
// not divisible by prime number P
static int func(int N, int P)
{
// Total sum upto N
int sumUptoN = (N * (N + 1) / 2);
int sumOfMultiplesOfP;
// If no multiple of P exist up to N
if (N < P)
{
return sumUptoN;
}
// If only P itself is in the range
// from 1 to N
else if ((N / P) == 1)
{
return sumUptoN - P + 1;
}
// Sum of those that are divisible by P
sumOfMultiplesOfP = ((N / P) * (2 * P +
(N / P - 1) * P)) / 2;
// Recursively function call to
// find the sum for N/P
return (sumUptoN + func(N / P, P) -
sumOfMultiplesOfP);
}
// Driver Code
public static void main(String[] args)
{
// Given N and P
int N = 10, P = 5;
// Function call
System.out.println(func(N, P));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the # above approach # Function to find the sum # of largest divisors of # numbers in range 1 to N # not divisible by prime number P def func(N, P): # Total sum upto N sumUptoN = (N * (N + 1) / 2); sumOfMultiplesOfP = 0; # If no multiple of P exist # up to N if (N < P): return sumUptoN; # If only P itself is # in the range from 1 # to N elif ((N / P) == 1): return sumUptoN - P + 1; # Sum of those that are # divisible by P sumOfMultiplesOfP = (((N / P) * (2 * P + (N / P - 1) * P)) / 2); # Recursively function call to # find the sum for N/P return (sumUptoN + func(N / P, P) - sumOfMultiplesOfP); # Driver Code if __name__ == '__main__': # Given N and P N = 10; P = 5; # Function call print(func(N, P)); # This code is contributed by Rajput-Ji
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the sum of largest
// divisors of numbers in range 1 to N
// not divisible by prime number P
static int func(int N, int P)
{
// Total sum upto N
int sumUptoN = (N * (N + 1) / 2);
int sumOfMultiplesOfP;
// If no multiple of P exist up to N
if (N < P)
{
return sumUptoN;
}
// If only P itself is in the range
// from 1 to N
else if ((N / P) == 1)
{
return sumUptoN - P + 1;
}
// Sum of those that are divisible by P
sumOfMultiplesOfP = ((N / P) * (2 * P +
(N / P - 1) * P)) / 2;
// Recursively function call to
// find the sum for N/P
return (sumUptoN + func(N / P, P) -
sumOfMultiplesOfP);
}
// Driver Code
public static void Main(String[] args)
{
// Given N and P
int N = 10, P = 5;
// Function call
Console.WriteLine(func(N, P));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program for the above approach
// Function to find the sum of largest
// divisors of numbers in range 1 to N
// not divisible by prime number P
function func(N, P)
{
// Total sum upto N
let sumUptoN = (N * (N + 1) / 2);
let sumOfMultiplesOfP;
// If no multiple of P exist up to N
if (N < P)
{
return sumUptoN;
}
// If only P itself is in the range
// from 1 to N
else if ((N / P) == 1)
{
return sumUptoN - P + 1;
}
// Sum of those that are divisible by P
sumOfMultiplesOfP = ((N / P) * (2 * P +
(N / P - 1) * P)) / 2;
// Recursively function call to
// find the sum for N/P
return (sumUptoN + func(N / P, P) -
sumOfMultiplesOfP);
}
// Driver Code
// Given N and P
let N = 10, P = 5;
// Function call
document.write(func(N, P));
</script>
43
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por KrishnaHare y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA