Dados dos números enteros N y K , la tarea es encontrar el número de arreglos diferentes de tamaño N que se pueden formar teniendo el primer elemento como K de modo que todos los elementos, excepto el último, sean divisibles por el siguiente elemento del arreglo. Dado que la cuenta puede ser muy grande, imprima el módulo 10 9 + 7 .
Ejemplos:
Entrada: N = 3, K = 5
Salida: 3
Explicación:
Hay 3 arrays válidas posibles que comienzan con el valor 5 que satisfacen los criterios dados:
- {5, 5, 5}
- {5, 5, 1}
- {5, 1, 1}.
Por lo tanto, la cuenta total es 3.
Entrada: N = 3, K = 6
Salida: 9
Enfoque: El problema dado se puede resolver usando la Teoría de Números y la Combinatoria . El primer elemento de la array es K , luego el siguiente elemento de la array es uno de los factores de K . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una variable, digamos res como 1 que almacene el recuento resultante de arrays formadas.
- Encuentre todas las potencias de los factores primos del número K y para cada factor primo P realice los siguientes pasos:
- Encuentre el número de veces que P ocurre en el valor K. Que la cuenta sea la cuenta .
- El número de formas posibles de mantener uno de los factores de P está dado por (N – cuenta + 1) C cuenta .
- Multiplique el valor (N – cuenta + 1) C cuenta con el valor res .
- Después de completar los pasos anteriores, imprima el valor de res como resultado.
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;
int MOD = 1000000007;
// Find the value of x raised to the
// yth power modulo MOD
long modPow(long x, long y)
{
// Stores the value of x^y
long r = 1, a = x;
// Iterate until y is positive
while (y > 0) {
if ((y & 1) == 1) {
r = (r * a) % MOD;
}
a = (a * a) % MOD;
y /= 2;
}
return r;
}
// Function to perform the Modular
// Multiplicative Inverse using the
// Fermat's little theorem
long modInverse(long x)
{
return modPow(x, MOD - 2);
}
// Modular division x / y, find
// modular multiplicative inverse
// of y and multiply by x
long modDivision(long p, long q)
{
return (p * modInverse(q)) % MOD;
}
// Function to find Binomial Coefficient
// C(n, k) in O(k) time
long C(long n, int k)
{
// Base Case
if (k > n) {
return 0;
}
long p = 1, q = 1;
for (int i = 1; i <= k; i++) {
// Update the value of p and q
q = (q * i) % MOD;
p = (p * (n - i + 1)) % MOD;
}
return modDivision(p, q);
}
// Function to find the count of arrays
// having K as the first element satisfying
// the given criteria
int countArrays(int N, int K)
{
// Stores the resultant count of arrays
long res = 1;
// Find the factorization of K
for (int p = 2; p <= K / p; p++) {
int c = 0;
// Stores the count of the exponent
// of the currentprime factor
while (K % p == 0) {
K /= p;
c++;
}
res = (res * C(N - 1 + c, c))
% MOD;
}
if (N > 1) {
// N is one last prime factor,
// for c = 1 -> C(N-1+1, 1) = N
res = (res * N) % MOD;
}
// Return the total count
return res;
}
// Driver Code
int main()
{
int N = 3, K = 5;
cout << countArrays(N, K);
return 0;
}
Java
// Java program for the above approach
class GFG {
public static int MOD = 1000000007;
// Find the value of x raised to the
// yth power modulo MOD
public static long modPow(long x, long y)
{
// Stores the value of x^y
long r = 1, a = x;
// Iterate until y is positive
while (y > 0) {
if ((y & 1) == 1) {
r = (r * a) % MOD;
}
a = (a * a) % MOD;
y /= 2;
}
return r;
}
// Function to perform the Modular
// Multiplicative Inverse using the
// Fermat's little theorem
public static long modInverse(long x) {
return modPow(x, MOD - 2);
}
// Modular division x / y, find
// modular multiplicative inverse
// of y and multiply by x
public static long modDivision(long p, long q) {
return (p * modInverse(q)) % MOD;
}
// Function to find Binomial Coefficient
// C(n, k) in O(k) time
public static long C(long n, int k) {
// Base Case
if (k > n) {
return 0;
}
long p = 1, q = 1;
for (int i = 1; i <= k; i++) {
// Update the value of p and q
q = (q * i) % MOD;
p = (p * (n - i + 1)) % MOD;
}
return modDivision(p, q);
}
// Function to find the count of arrays
// having K as the first element satisfying
// the given criteria
public static long countArrays(int N, int K) {
// Stores the resultant count of arrays
long res = 1;
// Find the factorization of K
for (int p = 2; p <= K / p; p++) {
int c = 0;
// Stores the count of the exponent
// of the currentprime factor
while (K % p == 0) {
K /= p;
c++;
}
res = (res * C(N - 1 + c, c)) % MOD;
}
if (N > 1) {
// N is one last prime factor,
// for c = 1 -> C(N-1+1, 1) = N
res = (res * N) % MOD;
}
// Return the total count
return res;
}
// Driver Code
public static void main(String args[]) {
int N = 3, K = 5;
System.out.println(countArrays(N, K));
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# python 3 program for the above approach MOD = 1000000007 from math import sqrt # Find the value of x raised to the # yth power modulo MOD def modPow(x, y): # Stores the value of x^y r = 1 a = x # Iterate until y is positive while(y > 0): if ((y & 1) == 1): r = (r * a) % MOD a = (a * a) % MOD y /= 2 return r # Function to perform the Modular # Multiplicative Inverse using the # Fermat's little theorem def modInverse(x): return modPow(x, MOD - 2) # Modular division x / y, find # modular multiplicative inverse # of y and multiply by x def modDivision(p, q): return (p * modInverse(q)) % MOD # Function to find Binomial Coefficient # C(n, k) in O(k) time def C(n, k): # Base Case if (k > n): return 0 p = 1 q = 1 for i in range(1,k+1,1): # Update the value of p and q q = (q * i) % MOD p = (p * (n - i + 1)) % MOD return modDivision(p, q) # Function to find the count of arrays # having K as the first element satisfying # the given criteria def countArrays(N, K): # Stores the resultant count of arrays res = 1 # Find the factorization of K for p in range(2,int(sqrt(K)),1): c = 0 # Stores the count of the exponent # of the currentprime factor while (K % p == 0): K /= p c += 1 res = (res * C(N - 1 + c, c)) % MOD if (N > 1): # N is one last prime factor, # for c = 1 -> C(N-1+1, 1) = N res = (res * N) % MOD # Return the total count return res # Driver Code if __name__ == '__main__': N = 3 K = 5 print(countArrays(N, K)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
public class GFG
{
public static int MOD = 1000000007;
// Find the value of x raised to the
// yth power modulo MOD
public static long modPow(long x, long y)
{
// Stores the value of x^y
long r = 1, a = x;
// Iterate until y is positive
while (y > 0) {
if ((y & 1) == 1) {
r = (r * a) % MOD;
}
a = (a * a) % MOD;
y /= 2;
}
return r;
}
// Function to perform the Modular
// Multiplicative Inverse using the
// Fermat's little theorem
public static long modInverse(long x) {
return modPow(x, MOD - 2);
}
// Modular division x / y, find
// modular multiplicative inverse
// of y and multiply by x
public static long modDivision(long p, long q) {
return (p * modInverse(q)) % MOD;
}
// Function to find Binomial Coefficient
// C(n, k) in O(k) time
public static long C(long n, int k) {
// Base Case
if (k > n) {
return 0;
}
long p = 1, q = 1;
for (int i = 1; i <= k; i++) {
// Update the value of p and q
q = (q * i) % MOD;
p = (p * (n - i + 1)) % MOD;
}
return modDivision(p, q);
}
// Function to find the count of arrays
// having K as the first element satisfying
// the given criteria
public static long countArrays(int N, int K) {
// Stores the resultant count of arrays
long res = 1;
// Find the factorization of K
for (int p = 2; p <= K / p; p++) {
int c = 0;
// Stores the count of the exponent
// of the currentprime factor
while (K % p == 0) {
K /= p;
c++;
}
res = (res * C(N - 1 + c, c)) % MOD;
}
if (N > 1) {
// N is one last prime factor,
// for c = 1 -> C(N-1+1, 1) = N
res = (res * N) % MOD;
}
// Return the total count
return res;
}
// Driver Code
static public void Main (){
int N = 3, K = 5;
Console.WriteLine(countArrays(N, K));
}
}
// This code is contributed by Dharanendra L V.
Javascript
<script>
// JavaScript Program to implement
// the above approach
let MOD = 1000000007;
// Find the value of x raised to the
// yth power modulo MOD
function modPow(x, y)
{
// Stores the value of x^y
let r = 1, a = x;
// Iterate until y is positive
while (y > 0) {
if ((y & 1) == 1) {
r = (r * a) % MOD;
}
a = (a * a) % MOD;
y /= 2;
}
return r;
}
// Function to perform the Modular
// Multiplicative Inverse using the
// Fermat's little theorem
function modInverse(x) {
return modPow(x, MOD - 2);
}
// Modular division x / y, find
// modular multiplicative inverse
// of y and multiply by x
function modDivision(p, q) {
return (p * modInverse(q)) % MOD;
}
// Function to find Binomial Coefficient
// C(n, k) in O(k) time
function C(n, k)
{
// Base Case
if (k > n) {
return 0;
}
let p = 1, q = 1;
for (let i = 1; i <= k; i++) {
// Update the value of p and q
q = (q * i) % MOD;
p = (p * (n - i + 1)) % MOD;
}
return modDivision(p, q);
}
// Function to find the count of arrays
// having K as the first element satisfying
// the given criteria
function countArrays(N, K)
{
// Stores the resultant count of arrays
let res = 1;
// Find the factorization of K
for (let p = 2; p <= K / p; p++) {
let c = 0;
// Stores the count of the exponent
// of the currentprime factor
while (K % p == 0) {
K /= p;
c++;
}
res = (res * C(N - 1 + c, c))
% MOD;
}
if (N > 1) {
// N is one last prime factor,
// for c = 1 -> C(N-1+1, 1) = N
res = (res * N) % MOD;
}
// Return the total count
return res;
}
// Driver Code
let N = 3, K = 5;
document.write(countArrays(N, K));
// This code is contributed by Potta Lokesh
</script>
Producción:
3
Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA