Jugadores mínimos requeridos para ganar el juego

Dadas N preguntas y K opciones para cada pregunta, donde $1\leq N \leq 1000000000$ y $1\leq K \leq 1000000000$ . La tarea es determinar la suma del número total de jugadores que han intentado con la pregunta para que todos $1 \leq i \leq N$ ganen el juego de todos modos. Tienes que minimizar la suma de un número total de jugadores y generarlo módulo 10 ⁹ +7 .

Nota: Cualquier respuesta incorrecta conduce a la eliminación del jugador.

Ejemplos:

Input: N = 3, K = 3
Output: 39

Input: N = 5, K = 2
Output: 62

Acercarse:

Para resolver la pregunta N se necesitan jugadores K.

Para resolver (N-1) la pregunta K se necesitan ^{2 jugadores.}

De manera similar, en adelante, para resolver la primera pregunta , se necesitan jugadores K ^N.

Entonces, nuestro problema se reduce a encontrar la suma de los términos GP K + K ² + … + K ^N que es igual a $\frac{K(K^{N}-1)}{K-1}$ .
Ahora podemos usar el pequeño teorema de Fermat para obtener el módulo de respuesta requerido con 10 ⁹ +7 .

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

C++

// C++ program to find minimum players
// required to win the game anyhow
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
 
// function to calculate (a^b)%(10^9+7).
long long int power(long long int a, long long int b)
{
    long long int res = 1;
    while (b) {
        if (b & 1) {
            res *= a;
            res %= mod;
        }
        b /= 2;
        a *= a;
        a %= mod;
    }
    return res;
}
 
// function to find the minimum required player
long long int minPlayer(long long int n, long long int k)
{
 
    // computing the nenomenator
    long long int num = ((power(k, n) - 1) + mod) % mod;
 
    // computing modulo inverse of denominator
    long long int den = (power(k - 1, mod - 2) + mod) % mod;
 
    // final result
    long long int ans = (((num * den) % mod) * k) % mod;
 
    return ans;
}
 
// Driver code
int main()
{
 
    long long int n = 3, k = 3;
 
    cout << minPlayer(n, k);
 
    return 0;
}

Java

//Java program to find minimum players
//required to win the game anyhow
public class TYU {
     
    static long  mod =  1000000007;
 
    //function to calculate (a^b)%(10^9+7).
     static long power(long a, long b)
     {
      long res = 1;
      while (b != 0) {
          if ((b & 1) != 0) {
              res *= a;
              res %= mod;
          }
          b /= 2;
          a *= a;
          a %= mod;
      }
      return res;
     }
 
     //function to find the minimum required player
     static long minPlayer(long n, long k)
     {
 
      // computing the nenomenator
      long num = ((power(k, n) - 1) + mod) % mod;
 
      // computing modulo inverse of denominator
      long den = (power(k - 1, mod - 2) + mod) % mod;
 
      // final result
      long ans = (((num * den) % mod) * k) % mod;
 
      return ans;
     }
 
     //Driver code
    public static void main(String[] args) {
         
         long n = 3, k = 3;
 
         System.out.println(minPlayer(n, k));
    }
}

Python 3

# Python 3 Program  to find minimum players
#  required to win the game anyhow
 
# constant
mod = 1000000007
 
# function to calculate (a^b)%(10^9+7).
def power(a, b) :
    res = 1
 
    while(b) :
        if (b & 1) :
            res *= a
            res %= mod
 
        b //= 2
        a *= a
        a %= mod
 
    return res
 
# function to find the minimum required player
def minPlayer(n, k) :
 
    # computing the nenomenator
    num = ((power(k, n) - 1) + mod) % mod
 
    # computing modulo inverse of denominator
    den = (power(k - 1,mod - 2) + mod) % mod
 
    # final result
    ans = (((num * den) % mod ) * k) % mod
 
    return ans
 
# Driver Code
if __name__ == "__main__" :
 
    n, k = 3, 3
 
    print(minPlayer(n, k))
 
# This code is contributed by ANKITRAI1

C#

// C# program to find minimum players
// required to win the game anyhow
using System;
class GFG
{
 
static long mod = 1000000007;
 
// function to calculate (a^b)%(10^9+7).
static long power(long a, long b)
{
long res = 1;
while (b != 0)
{
    if ((b & 1) != 0)
    {
        res *= a;
        res %= mod;
    }
    b /= 2;
    a *= a;
    a %= mod;
}
return res;
}
 
// function to find the minimum
// required player
static long minPlayer(long n, long k)
{
 
    // computing the nenomenator
    long num = ((power(k, n) - 1) + mod) % mod;
     
    // computing modulo inverse
    // of denominator
    long den = (power(k - 1, mod - 2) + mod) % mod;
     
    // final result
    long ans = (((num * den) % mod) * k) % mod;
     
    return ans;
}
 
// Driver code
public static void Main()
{
    long n = 3, k = 3;
 
    Console.WriteLine(minPlayer(n, k));
}
}
 
// This code is contributed
// by Shashank

PHP

<?php
// PHP program to find minimum players
// required to win the game anyhow
 
// function to calculate (a^b)%(10^9+7).
function power($a, $b)
{
    $mod = 1000000007;
    $res = 1;
    while ($b)
    {
        if ($b & 1)
        {
            $res *= $a;
            $res %= $mod;
        }
        $b /= 2;
        $a *= $a;
        $a %= $mod;
    }
    return $res;
}
 
// function to find the minimum
// required player
function minPlayer($n, $k)
{
    $mod =1000000007;
     
    // computing the nenomenator
    $num = ((power($k, $n) - 1) +
                   $mod) % $mod;
 
    // computing modulo inverse
    // of denominator
    $den = (power($k - 1, $mod - 2) +
                  $mod) % $mod;
 
    // final result
    $ans = ((($num * $den) % $mod) *
                       $k) % $mod;
 
    return $ans;
}
 
// Driver code
$n = 3;
$k = 3;
 
echo minPlayer($n, $k);
 
// This code is contributed
// by Shivi_Aggarwal
?>

Javascript

<script>
//javascript program to find minimum players
//required to win the game anyhow
 
 
    var mod = 107;
 
    // function to calculate (a^b)%(10^9+7).
    function power(a , b) {
        var res = 1;
        while (b != 0) {
            if ((b & 1) != 0) {
                res *= a;
                res = res%mod;
            }
            b = parseInt(b/2);
            a *= a;
            a %= mod;
        }
        return res;
    }
 
    // function to find the minimum required player
    function minPlayer(n , k) {
 
        // computing the nenomenator
        var num = ((power(k, n) - 1) + mod) % mod;
 
        // computing modulo inverse of denominator
        var den = (power(k - 1, mod - 2) + mod) % mod;
 
        // final result
        var ans = (((num * den) % mod) * k) % mod;
 
        return ans;
    }
 
    // Driver code
     
 
        var n = 3, k = 3;
 
        document.write(minPlayer(n, k));
 
// This code contributed by gauravrajput1
</script>

Producción:

Complejidad de Tiempo: O(log(n)), Espacio Auxiliar: O (1)

Publicación traducida automáticamente

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

C++

Java

Python 3

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta