Dados dos números N y M. Encuentra el número de formas en que el factorial N puede expresarse como una suma de dos o más números consecutivos. Imprime el resultado módulo M.
Ejemplos:
Input : N = 3, M = 7 Output : 1 Explanation: 3! can be expressed in one way, i.e. 1 + 2 + 3 = 6. Hence 1 % 7 = 1 Input : N = 4, M = 7 Output : 1 Explanation: 4! can be expressed in one way, i.e. 7 + 8 + 9 = 24 Hence 1 % 7 = 1
Una solución simple es primero calcular el factorial , luego contar el número de formas de representar el factorial como suma de números consecutivos usando Contar formas de expresar un número como suma de números consecutivos . Esta solución provoca desbordamiento.
A continuación se muestra una mejor solución para evitar el desbordamiento.
Consideremos que la suma de r números consecutivos se expresa como:
(a + 1) + (a + 2) + (a + 3) + … + (a + r), lo cual se simplifica como (r * (r + 2* a + 1)) / 2
Por lo tanto, (a + 1) + (a + 2) + (a + 3) + … + (a + r) = (r * (r + 2*a + 1)) / 2 Como la expresión anterior es igual al factorial N, la escribimos como
2 * N! = r * (r + 2*a + 1)
En lugar de contar todos los pares (r, a), contaremos todos los pares (r, r + 2*a + 1). ¡Ahora, solo estamos contando todos los pares ordenados (X, Y) con XY = 2 * N! donde X < Y y X, Y tienen paridad diferente, eso significa que si (r) es par, (r + 2*a + 1) es impar o si (r) es impar entonces (r + 2*a + 1) es incluso. ¡Esto es equivalente a encontrar los divisores impares de 2 * N! que será igual a los divisores impares de N!.
Para contar el número de divisores en N!, calculamos la potencia de los primos en factorización y el recuento total de divisores se convierte en (p 1 + 1) * (p 2 + 1) * … * (p n + 1). Para calcular la mayor potencia de un número primo en N!, utilizaremos la fórmula de legendre . 
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to count number of
// ways we can express a factorial
// as sum of consecutive numbers
#include <bits/stdc++.h>
using namespace std;
#define MAX 50002
vector<int> primes;
// sieve of Eratosthenes to compute
// the prime numbers
void sieve()
{
bool isPrime[MAX];
memset(isPrime, true, sizeof(isPrime));
for (int p = 2; p * p < MAX; p++) {
if (isPrime[p] == true) {
for (int i = p * 2; i < MAX; i += p)
isPrime[i] = false;
}
}
// Store all prime numbers
for (int p = 2; p < MAX; p++)
if (isPrime[p])
primes.push_back(p);
}
// function to calculate the largest
// power of a prime in a number
long long int power(long long int x,
long long int y)
{
long long int count = 0;
long long int z = y;
while (x >= z) {
count += (x / z);
z *= y;
}
return count;
}
// Modular multiplication to avoid
// the overflow of multiplication
// Please see below for details
// https://www.geeksforgeeks.org/how-to-avoid-overflow-in-modular-multiplication/
long long int modMult(long long int a,
long long int b,
long long int mod)
{
long long int res = 0;
a = a % mod;
while (b > 0) {
if (b % 2 == 1)
res = (res + a) % mod;
a = (a * 2) % mod;
b /= 2;
}
return res % mod;
}
// Returns count of ways to express n!
// as sum of consecutives.
long long int countWays(long long int n,
long long int m)
{
long long int ans = 1;
// We skip 2 (First prime) as we need to
// consider only odd primes
for (int i = 1; i < primes.size(); i++) {
// compute the largest power of prime
long long int powers = power(n, primes[i]);
// if the power of current prime number
// is zero in N!, power of primes greater
// than current prime number will also
// be zero, so break out from the loop
if (powers == 0)
break;
// multiply the result at every step
ans = modMult(ans, powers + 1, m) % m;
}
// subtract 1 to exclude the case of 1
// being an odd divisor
if (((ans - 1) % m) < 0)
return (ans - 1 + m) % m;
else
return (ans - 1) % m;
}
// Driver Code
int main()
{
sieve();
long long int n = 4, m = 7;
cout << countWays(n, m);
return 0;
}
Java
// Java program to count number of
// ways we can express a factorial
// as sum of consecutive numbers
import java.util.*;
class GFG {
static int MAX = 50002;
static ArrayList<Integer> primes
= new ArrayList<Integer>();
// sieve of Eratosthenes to compute
// the prime numbers
public static void sieve()
{
boolean isPrime[] = new boolean[MAX];
for(int i = 0; i < MAX; i++)
isPrime[i] = true;
for (int p = 2; p * p < MAX; p++) {
if (isPrime[p] == true) {
for (int i = p * 2; i < MAX; i += p)
isPrime[i] = false;
}
}
// Store all prime numbers
for (int p = 2; p < MAX; p++)
if (isPrime[p] == true)
primes.add(p);
}
// function to calculate the largest
// power of a prime in a number
public static int power(int x, int y)
{
int count = 0;
int z = y;
while (x >= z) {
count += (x / z);
z *= y;
}
return count;
}
// Modular multiplication to avoid
// the overflow of multiplication
// Please see below for details
// https://www.geeksforgeeks.org/how-to-avoid-overflow-in-modular-multiplication/
public static int modMult(int a, int b, int mod)
{
int res = 0;
a = a % mod;
while (b > 0) {
if (b % 2 == 1)
res = (res + a) % mod;
a = (a * 2) % mod;
b /= 2;
}
return res % mod;
}
// Returns count of ways to express n!
// as sum of consecutives.
public static int countWays(int n, int m)
{
int ans = 1;
// We skip 2 (First prime) as we need to
// consider only odd primes
for (int i = 1; i < primes.size(); i++) {
// compute the largest power of prime
int powers = power(n, primes.get(i));
// if the power of current prime number
// is zero in N!, power of primes greater
// than current prime number will also
// be zero, so break out from the loop
if (powers == 0)
break;
// multiply the result at every step
ans = modMult(ans, powers + 1, m) % m;
}
// subtract 1 to exclude the case of 1
// being an odd divisor
if (((ans - 1) % m) < 0)
return (ans - 1 + m) % m;
else
return (ans - 1) % m;
}
//Driver function
public static void main (String[] args) {
sieve();
int n = 4, m = 7;
System.out.println(countWays(n,m));
}
}
// This code is contributed by akash1295.
Python 3
# Python 3 program to count number of # ways we can express a factorial # as sum of consecutive numbers MAX = 50002; primes = [] # sieve of Eratosthenes to compute # the prime numbers def sieve(): isPrime = [True]*(MAX) p = 2 while p * p < MAX : if (isPrime[p] == True): for i in range( p * 2,MAX, p): isPrime[i] = False p+=1 # Store all prime numbers for p in range( 2,MAX): if (isPrime[p]): primes.append(p) # function to calculate the largest # power of a prime in a number def power( x, y): count = 0 z = y while (x >= z): count += (x // z) z *= y return count # Modular multiplication to avoid # the overflow of multiplication # Please see below for details # https://www.geeksforgeeks.org/how-to-avoid-overflow-in-modular-multiplication/ def modMult(a, b,mod): res = 0 a = a % mod while (b > 0): if (b % 2 == 1): res = (res + a) % mod a = (a * 2) % mod b //= 2 return res % mod # Returns count of ways to express n! # as sum of consecutives. def countWays(n,m): ans = 1 # We skip 2 (First prime) as we need to # consider only odd primes for i in range(1,len(primes)): # compute the largest power of prime powers = power(n, primes[i]) # if the power of current prime number # is zero in N!, power of primes greater # than current prime number will also # be zero, so break out from the loop if (powers == 0): break # multiply the result at every step ans = modMult(ans, powers + 1, m) % m # subtract 1 to exclude the case of 1 # being an odd divisor if (((ans - 1) % m) < 0): return (ans - 1 + m) % m else: return (ans - 1) % m # Driver Code if __name__ == "__main__": sieve() n = 4 m = 7 print(countWays(n, m)) # This code is contributed by ChitraNayal
C#
// C# program to count number of
// ways we can express a factorial
// as sum of consecutive numbers
using System ;
using System.Collections;
class GFG {
static int MAX = 50002;
static ArrayList primes = new ArrayList ();
// sieve of Eratosthenes to compute
// the prime numbers
public static void sieve()
{
bool []isPrime = new bool[MAX];
for(int i = 0; i < MAX; i++)
isPrime[i] = true;
for (int p = 2; p * p < MAX; p++) {
if (isPrime[p] == true) {
for (int i = p * 2; i < MAX; i += p)
isPrime[i] = false;
}
}
// Store all prime numbers
for (int p = 2; p < MAX; p++)
if (isPrime[p] == true)
primes.Add(p);
}
// function to calculate the largest
// power of a prime in a number
public static int power_prime(int x, int y)
{
int count = 0;
int z = y;
while (x >= z) {
count += (x / z);
z *= y;
}
return count;
}
// Modular multiplication to avoid
// the overflow of multiplication
// Please see below for details
// https://www.geeksforgeeks.org/how-to-avoid-overflow-in-modular-multiplication/
public static int modMult(int a, int b, int mod)
{
int res = 0;
a = a % mod;
while (b > 0) {
if (b % 2 == 1)
res = (res + a) % mod;
a = (a * 2) % mod;
b /= 2;
}
return res % mod;
}
// Returns count of ways to express n!
// as sum of consecutives.
public static int countWays(int n, int m)
{
int ans = 1;
// We skip 2 (First prime) as we need to
// consider only odd primes
for (int i = 1; i < primes.Count; i++) {
// compute the largest power of prime
int powers = power_prime(n, Convert.ToInt32(primes[i]));
// if the power of current prime number
// is zero in N!, power of primes greater
// than current prime number will also
// be zero, so break out from the loop
if (powers == 0)
break;
// multiply the result at every step
ans = modMult(ans, powers + 1, m) % m;
}
// subtract 1 to exclude the case of 1
// being an odd divisor
if (((ans - 1) % m) < 0)
return (ans - 1 + m) % m;
else
return (ans - 1) % m;
}
//Driver function
public static void Main () {
sieve();
int n = 4, m = 7;
Console.WriteLine(countWays(n,m));
}
}
// This code is contributed by Ryuga
Javascript
<script>
// Javascript program to count number of
// ways we can express a factorial
// as sum of consecutive numbers
let MAX = 50002;
let primes = [];
// sieve of Eratosthenes to compute
// the prime numbers
function sieve()
{
let isPrime = new Array(MAX);
for(let i = 0; i < MAX; i++)
isPrime[i] = true;
for (let p = 2; p * p < MAX; p++)
{
if (isPrime[p] == true)
{
for (let i = p * 2; i < MAX; i += p)
isPrime[i] = false;
}
}
// Store all prime numbers
for (let p = 2; p < MAX; p++)
if (isPrime[p] == true)
primes.push(p);
}
// function to calculate the largest
// power of a prime in a number
function power(x,y)
{
let count = 0;
let z = y;
while (x >= z) {
count += Math.floor(x / z);
z *= y;
}
return count;
}
// Modular multiplication to avoid
// the overflow of multiplication
// Please see below for details
// https://www.geeksforgeeks.org/how-to-avoid-overflow-in-modular-multiplication/
function modMult(a,b,mod)
{
let res = 0;
a = a % mod;
while (b > 0) {
if (b % 2 == 1)
res = (res + a) % mod;
a = (a * 2) % mod;
b = Math.floor(b/2);
}
return res % mod;
}
// Returns count of ways to express n!
// as sum of consecutives.
function countWays(n,m)
{
let ans = 1;
// We skip 2 (First prime) as we need to
// consider only odd primes
for (let i = 1; i < primes.length; i++) {
// compute the largest power of prime
let powers = power(n, primes[i]);
// if the power of current prime number
// is zero in N!, power of primes greater
// than current prime number will also
// be zero, so break out from the loop
if (powers == 0)
break;
// multiply the result at every step
ans = modMult(ans, powers + 1, m) % m;
}
// subtract 1 to exclude the case of 1
// being an odd divisor
if (((ans - 1) % m) < 0)
return (ans - 1 + m) % m;
else
return (ans - 1) % m;
}
//Driver function
sieve();
let n = 4, m = 7;
document.write(countWays(n,m));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA