Dados tres enteros N , R y P donde P es primo, la tarea es encontrar si N C R es divisible por P o no.
Ejemplos:
Entrada: N = 6, R = 2, P = 7
Salida: No
6 C 2 = 15 que no es divisible por 7.
Entrada: N = 7, R = 2, P = 3
Salida: Sí
7 C 2 = 21 que es divisible por 3
Enfoque: ¡Sabemos que N C R = N! / (R! * (N – R)!) . Ahora, usando la fórmula de Legendre , encuentre la mayor potencia de P que divide a cualquier N. , R! y (N-R)! digamos x1 , x2 y x3 respectivamente.
Para que N C R sea divisible por P , se debe cumplir la condición x1 > x2 + x3 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
// Function to return the highest
// power of p that divides n!
// implementing Legendre Formula
int getfactor(int n, int p)
{
int pw = 0;
while (n) {
n /= p;
pw += n;
}
// Return the highest power of p
// which divides n!
return pw;
}
// Function that returns true
// if nCr is divisible by p
bool isDivisible(int n, int r, int p)
{
// Find the highest powers of p
// that divide n!, r! and (n - r)!
int x1 = getfactor(n, p);
int x2 = getfactor(r, p);
int x3 = getfactor(n - r, p);
// If nCr is divisible by p
if (x1 > x2 + x3)
return true;
return false;
}
// Driver code
int main()
{
int n = 7, r = 2, p = 7;
if (isDivisible(n, r, p))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java Implementation of above approach
import java.io.*;
class GFG
{
// Function to return the highest
// power of p that divides n!
// implementing Legendre Formula
static int getfactor(int n, int p)
{
int pw = 0;
while (n != 0)
{
n /= p;
pw += n;
}
// Return the highest power of p
// which divides n!
return pw;
}
// Function to return N digits
// number which is divisible by D
static int isDivisible(int n, int r, int p)
{
// Find the highest powers of p
// that divide n!, r! and (n - r)!
int x1 = getfactor(n, p);
int x2 = getfactor(r, p);
int x3 = getfactor(n - r, p);
// If nCr is divisible by p
if (x1 > x2 + x3)
return 1;
return 0;
}
// Driver code
public static void main (String[] args)
{
int n = 7, r = 2, p = 7;
if (isDivisible(n, r, p) == 1)
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by krikti..
Python3
# Python3 implementation of the approach
# Function to return the highest
# power of p that divides n!
# implementing Legendre Formula
def getfactor(n, p) :
pw = 0;
while (n) :
n //= p;
pw += n;
# Return the highest power of p
# which divides n!
return pw;
# Function that returns true
# if nCr is divisible by p
def isDivisible(n, r, p) :
# Find the highest powers of p
# that divide n!, r! and (n - r)!
x1 = getfactor(n, p);
x2 = getfactor(r, p);
x3 = getfactor(n - r, p);
# If nCr is divisible by p
if (x1 > x2 + x3) :
return True;
return False;
# Driver code
if __name__ == "__main__" :
n = 7; r = 2; p = 7;
if (isDivisible(n, r, p)) :
print("Yes");
else :
print("No");
# This code is contributed by AnkitRai01
C#
// C# Implementation of above approach
using System;
class GFG
{
// Function to return the highest
// power of p that divides n!
// implementing Legendre Formula
static int getfactor(int n, int p)
{
int pw = 0;
while (n != 0)
{
n /= p;
pw += n;
}
// Return the highest power of p
// which divides n!
return pw;
}
// Function to return N digits
// number which is divisible by D
static int isDivisible(int n, int r, int p)
{
// Find the highest powers of p
// that divide n!, r! and (n - r)!
int x1 = getfactor(n, p);
int x2 = getfactor(r, p);
int x3 = getfactor(n - r, p);
// If nCr is divisible by p
if (x1 > x2 + x3)
return 1;
return 0;
}
// Driver code
static public void Main ()
{
int n = 7, r = 2, p = 7;
if (isDivisible(n, r, p) == 1)
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
// This code is contributed by ajit.
Javascript
<script>
// Javascript Implementation of above approach
// Function to return the highest
// power of p that divides n!
// implementing Legendre Formula
function getfactor(n, p)
{
let pw = 0;
while (n != 0)
{
n = parseInt(n / p, 10);
pw += n;
}
// Return the highest power of p
// which divides n!
return pw;
}
// Function to return N digits
// number which is divisible by D
function isDivisible(n, r, p)
{
// Find the highest powers of p
// that divide n!, r! and (n - r)!
let x1 = getfactor(n, p);
let x2 = getfactor(r, p);
let x3 = getfactor(n - r, p);
// If nCr is divisible by p
if (x1 > x2 + x3)
return 1;
return 0;
}
let n = 7, r = 2, p = 7;
if (isDivisible(n, r, p) == 1)
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes
Complejidad de tiempo: O (log p n)
Espacio Auxiliar: O(1)