Encuentra si nCr es divisible por el primo dado

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)

Publicación traducida automáticamente

Artículo escrito por krikti y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *