C++ 中赢得游戏的最小玩家数量

问题陈述

给定 N 个问题，每个问题有 K 个选项，其中 1 <= N <= 1000000000 且 1 <= K <= 1000000000。任务是确定所有 1 <= i <= k 为了无论如何赢得游戏，尝试过第 i 个问题的玩家总数之和。您必须最小化玩家总数之和并输出其模 109+7 的结果。

请注意，任何错误答案都会导致玩家被淘汰

示例

如果 N = 5 且 K = 2，则答案为 62。

算法

  • 解决第 N 个问题需要 K 个玩家。
  • 解决第 (N-1) 个问题需要 K2 个玩家。
  • 类似地继续，解决第 1 个问题需要 KN 个玩家。
  • 因此，我们的问题简化为找到等比数列项的总和 K + K2 + … + KN，它等于：K(Kn -1) / K -1

示例

#include <iostream>
#include <cmath>
#define MOD 1000000007
using namespace std;
long long int power(long long a, long long b) {
   long long res = 1;
   while (b) {
      if (b & 1) {
         res = res * a;
         res = res % MOD;
      }
      b = b / 2;
      a = a * a;
      a = a % MOD;
   }
   return res;
}
long long getMinPlayer(long long n, long long k) {
   long long num = ((power(k, n) - 1) + MOD) % MOD;
   long long den = (power(k - 1, MOD - 2) + MOD) % MOD;
   long long ans = (((num * den) % MOD) * k) % MOD;
   return ans;
}
int main() {
   long long n = 5, k = 2;
   cout << "Minimum pairs = " << getMinPlayer(n, k) << endl;
   return 0;
}

输出

当您编译并执行上述程序时。它生成以下输出 -

Minimum pairs = 62

更新于： 2019-11-22

111 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告