Dado un número N , la tarea es encontrar la suma de todos los divisores cuadrados perfectos de los números del 1 al N .
Ejemplos:
Entrada: N = 5
Salida: 9
Explicación: N = 5
Cuadrados perfectos divisores de 1 = 1.
Del mismo modo, cuadrados perfectos divisores de 2, 3 = 1.
Cuadrados perfectos divisores de 4 = 1, 4.
Cuadrados perfectos divisores de 5 = 1 (por supuesto, para cualquier número primo, solo 1 será el divisor de cuadrados perfectos)
Entonces, la suma total = 1+1+1+(1+4)+1 = 9.Entrada: N = 30
Salida: 126Entrada: N = 100
Salida: 910
Enfoque ingenuo: este enfoque se basa en el enfoque implementado en este artículo
. El problema anterior se puede resolver en O(N 1/k ) para cualquier K -ésimo divisor de potencia, donde N es el número hasta el cual tenemos que encontrar la suma. Esto se debe a que, en esta suma, cada número contribuirá suelo (N/p) o int (N/p) veces. Por lo tanto, al iterar a través de estas potencias perfectas, solo necesitamos sumar [p * int(N/p)] a la suma.
Complejidad de tiempo: O(√N)
Enfoque eficiente:
- Comencemos desde inicio = 2, encontremos el rango más grande (de inicio a fin) para el cual piso (N/(inicio 2 )) = piso (N/(final 2 ))
- La contribución de todos los cuadrados perfectos en el intervalo [inicio, final] contribuirá al suelo (N/(inicio 2 )) veces, por lo tanto, podemos actualizar este rango de una vez.
- La contribución para el rango [inicio, fin] se puede dar como:
piso(N/(inicio 2 ))*(sumaHasta(fin) – sumaHasta(inicio-1))
- ¿Cómo encontrar el rango?
Para un valor dado de inicio, el final se puede encontrar por
sqrt(N/K), donde K = piso(N/(inicio^2))
- Ahora el siguiente rango se puede encontrar sustituyendo start = end+1.
Complejidad temporal: O(N 1/3 ) como N/(x 2 ) no puede tomar más de N 1/3 valores diferentes para un valor fijo de N .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the
// sum of all perfect square
// divisors of numbers from 1 to N
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define int unsigned long long
// Function for finding inverse
// of a number iteratively
// Here we will find the inverse
// of 6, since it appears as
// denominator in the formula of
// sum of squares from 1 to N
int inv(int a)
{
int o = 1;
for (int p = MOD - 2;
p > 0; p >>= 1) {
if ((p & 1) == 1)
o = (o * a) % MOD;
a = (a * a) % MOD;
}
return o;
}
// Store the value of the inverse
// of 6 once as we don't need to call
// the function again and again
int inv6 = inv(6);
// Formula for finding the sum
// of first n squares
int sumOfSquares(int n)
{
n %= MOD;
return (((n * (n + 1))
% MOD * (2 * n + 1))
% MOD * inv6)
% MOD;
}
int sums(int n)
{
// No perfect square
// exists which is
// less than 4
if (n < 4)
return 0;
// Starting from 2, present value
// of start is denoted here as
// curStart
int curStart = 2, ans = 0;
int sqrtN = sqrt(n);
while (curStart <= n / curStart) {
int V = n / (curStart * curStart);
// Finding end of the segment
// for which the contribution
// will be same
int end = sqrt(n / V);
// Using the above mentioned
// formula to find ans % MOD
ans += (n / (curStart * curStart)
% MOD * (sumOfSquares(end)
+ MOD
- sumOfSquares(curStart - 1)))
% MOD;
if (ans >= MOD)
ans -= MOD;
// Now for mthe next iteration
// start will become end+1
curStart = end + 1;
}
// Finally returning the answer
return ans;
}
// Driver Code
int32_t main()
{
int input[] = { 5 };
for (auto x : input) {
cout << "sum of all perfect"
<< " square divisors from"
<< " 1 to " << x
<< " is: ";
// Here we are adding x
// because we have not
// counted 1 as perfect
// squares so if u want to
// add it you can just add
// that number to the ans
cout << x + sums(x) << endl;
}
return 0;
}
Java
// Java program to find the
// sum of all perfect square
// divisors of numbers from 1 to N
import java.util.*;
class GFG{
static final int MOD = 7;
// Function for finding inverse
// of a number iteratively
// Here we will find the inverse
// of 6, since it appears as
// denominator in the formula of
// sum of squares from 1 to N
static int inv(int a)
{
int o = 1;
for(int p = MOD - 2;
p > 0; p >>= 1)
{
if ((p & 1) == 1)
o = (o * a) % MOD;
a = (a * a) % MOD;
}
return o;
}
// Store the value of the inverse
// of 6 once as we don't need to call
// the function again and again
static int inv6 = inv(6);
// Formula for finding the sum
// of first n squares
static int sumOfSquares(int n)
{
n %= MOD;
return (((n * (n + 1)) %
MOD * (2 * n + 1)) %
MOD * inv6) % MOD;
}
static int sums(int n)
{
// No perfect square
// exists which is
// less than 4
if (n < 4)
return 0;
// Starting from 2, present value
// of start is denoted here as
// curStart
int curStart = 2, ans = 0;
int sqrtN = (int)Math.sqrt(n);
while (curStart <= n / curStart)
{
int V = n / (curStart * curStart);
// Finding end of the segment
// for which the contribution
// will be same
int end = (int)Math.sqrt(n / V);
// Using the above mentioned
// formula to find ans % MOD
ans += (n / (curStart * curStart) %
MOD * (sumOfSquares(end) + MOD -
sumOfSquares(curStart - 1))) % MOD;
if (ans >= MOD)
ans -= MOD;
// Now for mthe next iteration
// start will become end+1
curStart = end + 1;
}
// Finally returning the answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
int input[] = {5};
for(int x : input)
{
System.out.print("sum of all perfect " +
"square divisors from " +
"1 to " + x + " is: ");
// Here we are adding x
// because we have not
// counted 1 as perfect
// squares so if u want to
// add it you can just add
// that number to the ans
System.out.print(x + sums(x) + "\n");
}
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to find the
# sum of all perfect square
# divisors of numbers from 1 to N
from math import *
MOD = 1000000007
# Function for finding inverse
# of a number iteratively
# Here we will find the inverse
# of 6, since it appears as
# denominator in the formula of
# sum of squares from 1 to N
def inv (a):
o = 1
p = MOD - 2
while (p > 0):
if (p % 2 == 1):
o = (o * a) % MOD
a = (a * a) % MOD
p >>= 1
return o
# Store the value of the inverse
# of 6 once as we don't need to call
# the function again and again
inv6 = inv(6)
# Formula for finding the sum
# of first n squares
def sumOfSquares (n):
n %= MOD
return (((n * (n + 1)) %
MOD * (2 * n + 1)) %
MOD * inv6) % MOD
def sums (n):
# No perfect square exists which
# is less than 4
if (n < 4):
return 0
# Starting from 2, present value
# of start is denoted here as curStart
curStart = 2
ans = 0
sqrtN = int(sqrt(n))
while (curStart <= n // curStart):
V = n // (curStart * curStart)
# Finding end of the segment for
# which the contribution will be same
end = int(sqrt(n // V))
# Using the above mentioned
# formula to find ans % MOD
ans += ((n // (curStart * curStart) %
MOD * (sumOfSquares(end) +
MOD - sumOfSquares(curStart - 1))) % MOD)
if (ans >= MOD):
ans -= MOD
# Now for mthe next iteration
# start will become end+1
curStart = end + 1
# Finally return the answer
return ans
# Driver Code
if __name__ == '__main__':
Input = [5]
for x in Input:
print("sum of all perfect "\
"square " , end = '')
print("divisors from 1 to", x,
"is: ", end = '')
# Here we are adding x because we have
# not counted 1 as perfect squares so if u
# want to add it you can just add that
# number to the ans
print(x + sums(x))
# This code is contributed by himanshu77
C#
// C# program to find the
// sum of all perfect square
// divisors of numbers from 1 to N
using System;
class GFG{
static readonly int MOD = 7;
// Function for finding inverse
// of a number iteratively
// Here we will find the inverse
// of 6, since it appears as
// denominator in the formula of
// sum of squares from 1 to N
static int inv(int a)
{
int o = 1;
for(int p = MOD - 2;
p > 0; p >>= 1)
{
if ((p & 1) == 1)
o = (o * a) % MOD;
a = (a * a) % MOD;
}
return o;
}
// Store the value of the inverse
// of 6 once as we don't need to call
// the function again and again
static int inv6 = inv(6);
// Formula for finding the sum
// of first n squares
static int sumOfSquares(int n)
{
n %= MOD;
return (((n * (n + 1)) %
MOD * (2 * n + 1)) %
MOD * inv6) % MOD;
}
static int sums(int n)
{
// No perfect square
// exists which is
// less than 4
if (n < 4)
return 0;
// Starting from 2, present
// value of start is denoted
// here as curStart
int curStart = 2, ans = 0;
int sqrtN = (int)Math.Sqrt(n);
while (curStart <= n / curStart)
{
int V = n / (curStart * curStart);
// Finding end of the segment
// for which the contribution
// will be same
int end = (int)Math.Sqrt(n / V);
// Using the above mentioned
// formula to find ans % MOD
ans += (n / (curStart * curStart) %
MOD * (sumOfSquares(end) + MOD -
sumOfSquares(curStart -
1))) % MOD;
if (ans >= MOD)
ans -= MOD;
// Now for mthe next iteration
// start will become end+1
curStart = end + 1;
}
// Finally returning
// the answer
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int []input = {5};
foreach(int x in input)
{
Console.Write("sum of all perfect " +
"square divisors from " +
"1 to " + x + " is: ");
// Here we are adding x
// because we have not
// counted 1 as perfect
// squares so if u want to
// add it you can just add
// that number to the ans
Console.Write(x + sums(x) + "\n");
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find the
// sum of all perfect square
// divisors of numbers from 1 to N
let MOD = 7;
// Function for finding inverse
// of a number iteratively
// Here we will find the inverse
// of 6, since it appears as
// denominator in the formula of
// sum of squares from 1 to N
function inv(a) {
let o = 1;
for (let p = MOD - 2;
p > 0; p >>= 1) {
if ((p & 1) == 1)
o = (o * a) % MOD;
a = (a * a) % MOD;
}
return o;
}
// Store the value of the inverse
// of 6 once as we don't need to call
// the function again and again
let inv6 = inv(6);
// Formula for finding the sum
// of first n squares
function sumOfSquares(n) {
n %= MOD;
return (((n * (n + 1)) %
MOD * (2 * n + 1)) %
MOD * inv6) % MOD;
}
function sums(n) {
// No perfect square
// exists which is
// less than 4
if (n < 4)
return 0;
// Starting from 2, present value
// of start is denoted here as
// curStart
let curStart = 2, ans = 0;
let sqrtN = Math.floor(Math.sqrt(n));
while (curStart <= Math.floor(n / curStart)) {
let V = Math.floor(n / (curStart * curStart));
// Finding end of the segment
// for which the contribution
// will be same
let end = Math.floor(Math.sqrt(n / V));
// Using the above mentioned
// formula to find ans % MOD
ans += (Math.floor(n / (curStart * curStart)) %
MOD * (sumOfSquares(end) + MOD -
sumOfSquares(curStart - 1))) % MOD;
if (ans >= MOD)
ans -= MOD;
// Now for mthe next iteration
// start will become end+1
curStart = end + 1;
}
// Finally returning the answer
return ans;
}
// Driver Code
let input = [5];
for (let x of input) {
document.write("sum of all perfect " +
"square divisors from " +
"1 to " + x + " is: ");
// Here we are adding x
// because we have not
// counted 1 as perfect
// squares so if u want to
// add it you can just add
// that number to the ans
document.write(x + sums(x) + "<br>");
}
// This code is contributed by Saurabh Jaiswal
</script>
Producción:
sum of all perfect square divisors from 1 to 5 is: 9
Complejidad de tiempo: O (N 1/3 )
Publicación traducida automáticamente
Artículo escrito por the_solver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA