Dado un número n, encuentre el producto de todos los factores de n. Dado que el producto puede ser muy grande, respóndalo módulo 10^9 + 7.
Ejemplos:
Input : 12 Output : 1728 1 * 2 * 3 * 4 * 6 * 12 = 1728 Input : 18 Output : 5832 1 * 2 * 3 * 6 * 9 * 18 = 5832
Método 1 (enfoque ingenuo):
podemos ejecutar el bucle para i de 1 an y si n es divisible por i multiplicar los números. La complejidad del tiempo para esta solución será O(n).
Pero este enfoque es insuficiente para valores grandes de n.
Método 2 (mejor enfoque):
un mejor enfoque es ejecutar el bucle para i de 1 a sqrt (n). Si el número es divisible por lo multiplico con i y n/i.
La complejidad temporal de esta solución será O(sqrt(n)).
C++
// C++ program to calculate product
// of factors of number
#include <bits/stdc++.h>
#define M 1000000007
using namespace std;
// function to product the factors
long long multiplyFactors(int n)
{
long long prod = 1;
for (int i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
// If factors are equal,
// multiply only once
if (n / i == i)
prod = (prod * i) % M;
// Otherwise multiply both
else {
prod = (prod * i) % M;
prod = (prod * n / i) % M;
}
}
}
return prod;
}
// Driver code
int main()
{
int n = 12;
cout << multiplyFactors(n) << endl;
return 0;
}
Java
// Java program to calculate product
// of factors of number
class GFG
{
public static final long M = 1000000007;
// function to product the factors
static long multiplyFactors(int n)
{
long prod = 1;
for (int i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
// If factors are equal,
// multiply only once
if (n / i == i)
prod = (prod * i) % M;
// Otherwise multiply both
else {
prod = (prod * i) % M;
prod = (prod * n / i) % M;
}
}
}
return prod;
}
// Driver Code
public static void main(String[] args)
{
int n = 12;
System.out.println(multiplyFactors(n));
}
}
Python
# Python program to calculate product # of factors of number M = 1000000007 # function to product the factors def multiplyFactors(n) : prod = 1 i = 1 while i * i <= n : if (n % i == 0) : # If factors are equal, # multiply only once if (n / i == i) : prod = (prod * i) % M #Otherwise multiply both else : prod = (prod * i) % M prod = (prod * n / i) % M i = i + 1 return prod # Driver Code n = 12 print (multiplyFactors(n)) # This code is contributed by Nikita Tiwari.
C#
//C# program to calculate product
// of factors of number
using System;
class GFG
{
public static long M = 1000000007;
// function to product the factors
static long multiplyFactors(int n)
{
long prod = 1;
for (int i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
// If factors are equal,
// multiply only once
if (n / i == i)
prod = (prod * i) % M;
// Otherwise multiply both
else {
prod = (prod * i) % M;
prod = (prod * n / i) % M;
}
}
}
return prod;
}
// Driver Code
public static void Main()
{
int n = 12;
Console.Write(multiplyFactors(n));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to calculate product
// of factors of number
$M = 1000000007;
// function to product the factors
function multiplyFactors( $n)
{
global $M;
$prod = 1;
for($i = 1; $i * $i <= $n; $i++)
{
if ($n % $i == 0)
{
// If factors are equal,
// multiply only once
if ($n / $i == $i)
$prod = ($prod * $i) % $M;
// Otherwise multiply both
else
{
$prod = ($prod * $i) % $M;
$prod = ($prod * $n / $i) % $M;
}
}
}
return $prod;
}
// Driver Code
$n = 12;
echo multiplyFactors($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to calculate product
// of factors of number
// function to product the factors
function multiplyFactors( n)
{
let M = 1000000007;
let i;
prod = 1;
for(i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
// If factors are equal,
// multiply only once
if (n / i == i)
prod = (prod * i) % M;
// Otherwise multiply both
else
{
prod = (prod * i) % M;
prod = (prod * n / i) % M;
}
}
}
return prod;
}
// Driver Code
n = 12;
document.write(multiplyFactors(n));
// This code is contributed by sravan
</script>
Producción :
1728
Complejidad temporal: O(√n)
Espacio auxiliar: O(1)
Método 3 (Otro Enfoque):
Observemos una cosa:
All factors of 12 are: 1, 2, 3, 4, 6, 12 1 * 2 * 3 * (2*2) * (2*3) * (2*2*3) = 2^6 * 3^3 = 12^3 and number of factors are 6
Entonces podemos observar que el producto de factores será n^(número de factor/2). Pero cuando el número de factor es impar (lo que significa que el número es un cuadrado perfecto), en ese caso el producto será n^(número de factor/2) * sqrt(n). Podemos contar el número de factores similares al enfoque anterior. Y podemos calcular la potencia de manera eficiente usando Exponenciación Modular
C++
// C++ program to calculate product
// of factors of number
#include <bits/stdc++.h>
#define M 1000000007
using namespace std;
// Iterative Function to calculate
// (x^y) in O(log y)
long long power(long long x, long long y)
{
long long res = 1;
while (y > 0)
{
if (y & 1)
res = (res * x) % M;
y = (y >> 1) % M;
x = (x * x) % M;
}
return res;
}
// function to count the factors
int countFactors(int n)
{
int count = 0;
for (int i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
// If factors are equal,
// count only once
if (n / i == i)
count++;
// Otherwise count both
else
count += 2;
}
}
return count;
}
long long multiplyFactors(int n)
{
int numFactor = countFactors(n);
// Calculate product of factors
long long product = power(n, numFactor / 2);
// If numFactor is odd return
// power(n, numFactor/2) * sqrt(n)
if (numFactor & 1)
product = (product * (int)sqrt(n)) % M;
return product;
}
// Driver code
int main()
{
int n = 12;
cout << multiplyFactors(n) << endl;
return 0;
}
Java
// Java program to calculate product
// of factors of number
class GFG
{
public static final long M = 1000000007;
// Iterative Function to calculate
// (x^y) in O(log y)
static long power(long x, long y)
{
long res = 1;
while (y > 0)
{
if (y % 2 == 1)
res = (res * x) % M;
y = (y >> 1) % M;
x = (x * x) % M;
}
return res;
}
// function to count the factors
static int countFactors(int n)
{
int count = 0;
for (int i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
// If factors are equal,
// count only once
if (n / i == i)
count++;
// Otherwise count both
else
count += 2;
}
}
return count;
}
static long multiplyFactors(int n)
{
int numFactor = countFactors(n);
// Calculate product of factors
long product = power(n, numFactor / 2);
// If numFactor is odd return
// power(n, numFactor/2) * sqrt(n)
if (numFactor % 2 == 1)
product = (product * (int)Math.sqrt(n)) % M;
return product;
}
// Driver Code
public static void main(String[] args)
{
int n = 12;
System.out.println(multiplyFactors(n));
}
}
Python
# Python program to calculate product # of factors of number M = 1000000007 # Iterative Function to calculate # (x^y) in O(log y) def power(x, y) : res = 1 while (y > 0) : if (y % 2 == 1) : res = (res * x) % M y = (y >> 1) % M x = (x * x) % M return res # function to count the factors def countFactors(n) : count = 0 i = 1 while i * i <= n : if (n % i == 0) : # If factors are equal, # count only once if (n / i == i) : count = count + 1 # Otherwise count both else : count = count + 2 i = i + 1 return count def multiplyFactors(n) : numFactor = countFactors(n) # Calculate product of factors product = power(n, numFactor / 2) # If numFactor is odd return # power(n, numFactor/2) * sqrt(n) if (numFactor % 2 == 1) : product = (product * (int)(math.sqrt(n))) % M return product # Driver Code n = 12 print multiplyFactors(n) # This code is contributed by Nikita Tiwari.
C#
// C# program to calculate product
// of factors of number
using System;
class GFG {
public static long M = 1000000007;
// Iterative Function to calculate
// (x^y) in O(log y)
static long power(long x, long y)
{
long res = 1;
while (y > 0)
{
if (y % 2 == 1)
res = (res * x) % M;
y = (y >> 1) % M;
x = (x * x) % M;
}
return res;
}
// function to count the factors
static int countFactors(int n)
{
int count = 0;
for (int i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
// If factors are equal,
// count only once
if (n / i == i)
count++;
// Otherwise count both
else
count += 2;
}
}
return count;
}
static long multiplyFactors(int n)
{
int numFactor = countFactors(n);
// Calculate product of factors
long product = power(n, numFactor / 2);
// If numFactor is odd return
// power(n, numFactor/2) * sqrt(n)
if (numFactor % 2 == 1)
product = (product *
(int)Math.Sqrt(n)) % M;
return product;
}
// Driver Code
public static void Main()
{
int n = 12;
Console.Write(multiplyFactors(n));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// PHP program to calculate product
// of factors of number
$M = 1000000007;
// Iterative Function to calculate
// (x^y) in O(log y)
function power( $x, $y)
{
global $M;
$res = 1;
while ($y > 0)
{
if ($y & 1)
$res = ($res * $x) % $M;
$y = ($y >> 1) % $M;
$x = ($x *$x) % $M;
}
return $res;
}
// function to count the factors
function countFactors( $n)
{
$count = 0;
for ($i = 1; $i * $i <= $n; $i++)
{
if ($n % $i == 0)
{
// If factors are equal,
// count only once
if ($n / $i == $i)
$count++;
// Otherwise count both
else
$count += 2;
}
}
return $count;
}
function multiplyFactors( $n)
{
$numFactor = countFactors($n);
// Calculate product of factors
$product = power($n, $numFactor / 2);
// If numFactor is odd return
// power(n, numFactor/2) * sqrt(n)
if ($numFactor & 1)
$product = ($product * sqrt($n)) % $M;
return $product;
}
// Driver code
$n = 12;
echo multiplyFactors($n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to calculate product
// of factors of number
let M = 1000000007;
// Iterative Function to calculate
// (x^y) in O(log y)
function power(x, y)
{
let res = 1;
while (y > 0)
{
if (y % 2 == 1)
res = (res * x) % M;
y = (y >> 1) % M;
x = (x * x) % M;
}
return res;
}
// function to count the factors
function countFactors(n)
{
let count = 0;
for (let i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
// If factors are equal,
// count only once
if (n / i == i)
count++;
// Otherwise count both
else
count += 2;
}
}
return count;
}
function multiplyFactors(n)
{
let numFactor = countFactors(n);
// Calculate product of factors
let product = power(n, numFactor / 2);
// If numFactor is odd return
// power(n, numFactor/2) * sqrt(n)
if (numFactor % 2 == 1)
product = (product * Math.sqrt(n)) % M;
return product;
}
// driver function
let n = 12;
document.write(multiplyFactors(n));
</script>
Producción :
1728
Complejidad temporal: O(√n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y nuclode . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA