¡Cuenta formas de dividir N! en dos factores coprimos distintos

Dado un número entero N , la tarea es encontrar el número de formas en que N! se puede dividir en dos factores distintos A y B , de modo que A y B son coprimos . Como la respuesta puede ser muy grande, imprímela módulo 10 ⁹ + 7 .

Ejemplos:

Entrada: N = 5
Salida: 4
Explicación: Los pares son (1, 120), (3, 40), (5, 24), (8, 15).

Entrada: N = 7
Salida: 8
Explicación: Los pares son (1, 5040), (5, 1008), (7, 720), (9, 560), (16, 315), (35, 144), ( 45, 112), (63, 80).

Enfoque ingenuo: ¡ El enfoque más simple es calcular el factorial de N! y genera todos sus factores y verifica si algún par de factores (i, j) tiene MCD (i, j) == 1 . 

Complejidad de Tiempo: O(√N!)
Espacio Auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es encontrar distintos factores primos de N y luego contar formas de dividirlo en dos factores coprimos distintos A y B. Siga los pasos a continuación para resolver el problema:

• Todo entero positivo se puede representar como un producto de potencias de números primos ( descomposición en factores primos ). Por lo tanto, cada valor posible de N se puede expresar como N = 2 ^p × 3 ^q × 5 ^r …..(p ≥ 0, q ≥ 0, r ≥ 0) .
• Ahora, la tarea es dividir N en dos factores coprimos distintos. Esto se puede hacer asignando cada uno de los términos en factorización prima de N en dos combinaciones posibles cada vez.

Ilustración:

Sea N = 18900 . 
Expresando N en forma de sus factores primos, 18900 = 2 ² * 3 ³ * 5 ² * 7 ¹

Cada uno de 2 ² , 3 ³ , 5 ² y 7 ¹ se puede asignar a cualquiera de los dos factores. Usando la regla del producto en combinatoria , el total de formas posibles es 2 ⁴ = 16 . Como los dos factores no tienen orden, el total de formas posibles es 2 ³ = 8 . Por lo tanto, el número de formas de N es 2 ^{X – 1} , donde X es el número de factores primos de N .

Siga los pasos a continuación para resolver el problema:

1. La descomposición en factores primos de N! contiene todos los primos que son menores o iguales a N .
2. Si x es el número de números primos menores o iguales que N , entonces el número de formas en que N! (factorial) se puede dividir en dos factores coprimos distintos es igual a 2 ^{x – 1} .
3. Calcule previamente el número de números primos ∀ n ≤ N usando la criba de Eratóstenes y guárdelos en una array.
4. Para calcular el resultado módulo 10 ⁹ + 7 , utilice la Exponenciación Modular , es decir, calcule x ^y % p .

A continuación se muestra la implementación del enfoque anterior:

// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Maximum value of N
#define MAXN 1000000
 
// Stores at each indices if
// given number is prime or not
int is_prime[MAXN] = { 0 };
 
// Stores count_of_primes
int count_of_primes[MAXN] = { 0 };
 
// Function to generate primes
// using Sieve of Eratosthenes
void sieve()
{
    for (int i = 3; i < MAXN; i += 2) {
 
        // Assume all odds are primes
        is_prime[i] = 1;
    }
 
    for (int i = 3; i * i < MAXN; i += 2) {
 
        // If a prime is encountered
        if (is_prime[i])
 
            for (int j = i * i; j < MAXN;
                 j += i) {
 
                // Mark all its multiples
                // as non-prime
                is_prime[j] = 0;
            }
    }
 
    is_prime[2] = 1;
 
    // Count primes <= MAXN
    for (int i = 1; i < MAXN; i++)
        count_of_primes[i]
            = count_of_primes[i - 1]
              + is_prime[i];
}
 
// Function to calculate (x ^ y) % p
// in O(log y)
long long int power(long long int x,
                    long long int y,
                    long long int p)
{
    long long result = 1;
    while (y > 0) {
        if (y & 1 == 1)
            result = (result * x) % p;
        x = (x * x) % p;
        y >>= 1;
    }
    return result;
}
 
// Utility function to count the number of ways
// N! can be split into co-prime factors
void numberOfWays(int N)
{
    long long int count
        = count_of_primes[N] - 1;
    long long int mod = 1000000007;
    long long int answer
        = power(2, count, mod);
 
    if (N == 1)
        answer = 0;
 
    cout << answer;
}
 
// Driver Code
int main()
{
    // Calling sieve function
    sieve();
 
    // Given N
    int N = 7;
 
    // Function call
    numberOfWays(N);
 
    return 0;
}

// Java Program for the above approach
import java.util.*;
 
class GFG {
 
    // Maximum value of N
    static final int MAXN = 1000000;
 
    // Stores at each indices if
    // given number is prime or not
    static int is_prime[];
 
    // Stores count_of_primes
    static int count_of_primes[];
 
    // Function to generate primes
    // using Sieve of Eratosthenes
    static void sieve()
    {
        is_prime = new int[MAXN];
        count_of_primes = new int[MAXN];
        Arrays.fill(is_prime, 0);
        Arrays.fill(count_of_primes, 0);
 
        for (int i = 3; i < MAXN; i += 2) {
 
            // Assume all odds are primes
            is_prime[i] = 1;
        }
 
        for (int i = 3; i * i < MAXN; i += 2) {
 
            // If a prime is encountered
            if (is_prime[i] == 1) {
                for (int j = i * i; j < MAXN;
                     j += i) {
                    // MArk all its multiples
                    // as non-prime
                    is_prime[j] = 0;
                }
            }
        }
 
        is_prime[2] = 1;
 
        // Count all primes upto MAXN
        for (int i = 1; i < MAXN; i++)
            count_of_primes[i]
                = count_of_primes[i - 1] + is_prime[i];
    }
 
    // Function to calculate (x ^ y) % p
    // in O(log y)
    static long power(long x, long y, long p)
    {
        long result = 1;
        while (y > 0) {
            if ((y & 1) == 1)
                result = (result * x) % p;
            x = (x * x) % p;
            y >>= 1;
        }
        return result;
    }
 
    // Utility function to count the number of
    // ways N! can be split into two co-prime factors
    static void numberOfWays(int N)
    {
        long count = count_of_primes[N] - 1;
        long mod = 1000000007;
        long answer = power(2, count, mod);
        if (N == 1)
            answer = 0;
        long ans = answer;
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Calling sieve function
        sieve();
 
        // Given N
        int N = 7;
 
        // Function call
        numberOfWays(N);
    }
}

# Python3 program for the above approach
import math
 
# Maximum value of N
MAXN = 1000000
 
# Stores at each indices if
# given number is prime or not
is_prime = [0] * MAXN
 
# Stores count_of_primes
count_of_primes = [0] * MAXN
 
# Function to generate primes
# using Sieve of Eratosthenes
def sieve():
     
    for i in range(3, MAXN, 2):
         
        # Assume all odds are primes
        is_prime[i] = 1
 
    for i in range(3, int(math.sqrt(MAXN)), 2):
 
        # If a prime is encountered
        if is_prime[i]:
            for j in range(i * i, MAXN, i):
 
                # Mark all its multiples
                # as non-prime
                is_prime[j] = 0
 
    is_prime[2] = 1
 
    # Count primes <= MAXN
    for i in range(1, MAXN):
        count_of_primes[i] = (count_of_primes[i - 1] +
                                     is_prime[i])
 
# Function to calculate (x ^ y) % p
# in O(log y)
def power(x, y, p):
   
    result = 1
    while (y > 0):
        if y & 1 == 1:
            result = (result * x) % p
             
        x = (x * x) % p
        y >>= 1
 
    return result
 
# Utility function to count the number of ways
# N! can be split into co-prime factors
def numberOfWays(N):
   
    count = count_of_primes[N] - 1
    mod = 1000000007
    answer = power(2, count, mod)
 
    if N == 1:
        answer = 0
 
    print(answer)
 
# Driver Code
if __name__ == "__main__":
   
    # Calling sieve function
    sieve()
 
    # Given N
    N = 7
 
    # Function call
    numberOfWays(N)
 
# This code is contributed by akhilsaini

// C# program for the above approach
using System;
 
class GFG{
 
// Maximum value of N
static int MAXN = 1000000;
 
// Stores at each indices if
// given number is prime or not
static int[] is_prime;
 
// Stores count_of_primes
static int[] count_of_primes;
 
// Function to generate primes
// using Sieve of Eratosthenes
static void sieve()
{
    is_prime = new int[MAXN];
    count_of_primes = new int[MAXN];
    Array.Fill(is_prime, 0);
    Array.Fill(count_of_primes, 0);
 
    for(int i = 3; i < MAXN; i += 2)
    {
         
        // Assume all odds are primes
        is_prime[i] = 1;
    }
 
    for(int i = 3; i * i < MAXN; i += 2)
    {
         
        // If a prime is encountered
        if (is_prime[i] == 1)
        {
            for(int j = i * i; j < MAXN; j += i)
            {
                 
                // MArk all its multiples
                // as non-prime
                is_prime[j] = 0;
            }
        }
    }
 
    is_prime[2] = 1;
 
    // Count all primes upto MAXN
    for(int i = 1; i < MAXN; i++)
        count_of_primes[i] = count_of_primes[i - 1] +
                                    is_prime[i];
}
 
// Function to calculate (x ^ y) % p
// in O(log y)
static long power(long x, long y, long p)
{
    long result = 1;
    while (y > 0)
    {
        if ((y & 1) == 1)
            result = (result * x) % p;
             
        x = (x * x) % p;
        y >>= 1;
    }
    return result;
}
 
// Utility function to count the number of
// ways N! can be split into two co-prime factors
static void numberOfWays(int N)
{
    long count = count_of_primes[N] - 1;
    long mod = 1000000007;
    long answer = power(2, count, mod);
     
    if (N == 1)
        answer = 0;
         
    long ans = answer;
    Console.Write(ans);
}
 
// Driver Code
public static void Main()
{
     
    // Calling sieve function
    sieve();
 
    // Given N
    int N = 7;
 
    // Function call
    numberOfWays(N);
}
}
 
// This code is contributed by akhilsaini

<script>
 
// Javascript Program for the above approach
 
// Maximum value of N
var MAXN = 1000000
 
// Stores at each indices if
// given number is prime or not
var is_prime = Array(MAXN).fill(0);
 
// Stores count_of_primes
var count_of_primes = Array(MAXN).fill(0);
 
// Function to generate primes
// using Sieve of Eratosthenes
function sieve()
{
    for (var i = 3; i < MAXN; i += 2) {
 
        // Assume all odds are primes
        is_prime[i] = 1;
    }
 
    for (var i = 3; i * i < MAXN; i += 2) {
 
        // If a prime is encountered
        if (is_prime[i])
 
            for (var j = i * i; j < MAXN;
                 j += i) {
 
                // Mark all its multiples
                // as non-prime
                is_prime[j] = 0;
            }
    }
 
    is_prime[2] = 1;
 
    // Count primes <= MAXN
    for (var i = 1; i < MAXN; i++)
        count_of_primes[i]
            = count_of_primes[i - 1]
              + is_prime[i];
}
 
// Function to calculate (x ^ y) % p
// in O(log y)
function power(x, y, p)
{
    var result = 1;
    while (y > 0) {
        if (y & 1 == 1)
            result = (result * x) % p;
        x = (x * x) % p;
        y >>= 1;
    }
    return result;
}
 
// Utility function to count the number of ways
// N! can be split into co-prime factors
function numberOfWays(N)
{
    var count
        = count_of_primes[N] - 1;
    var mod = 1000000007;
    var answer
        = power(2, count, mod);
 
    if (N == 1)
        answer = 0;
 
    document.write( answer);
}
 
// Driver Code
// Calling sieve function
sieve();
// Given N
var N = 7;
// Function call
numberOfWays(N);
 
</script>

8

Complejidad de tiempo: O(log(log(N)) + log(N))
Espacio auxiliar: O(N)