C++でゲームに勝つために必要な最小プレーヤー

問題の説明

1 <=N<=1000000000および1<=K <=1000000000の場合、N個の質問と各質問にK個のオプションが与えられます。タスクは、すべての1 <=i<に対してi番目の質問を試みたプレーヤーの総数を決定することです。 =とにかくゲームに勝つためのk。プレーヤーの総数の合計を最小化し、109+7を法として出力する必要があります。

間違った答えはプレーヤーの排除につながることに注意してください

例

N=5およびK=2の場合、答えは62です。

アルゴリズム

• N ^th を解決するには 質問Kプレーヤーが必要です。
• （N-1）を解決するには ^th 質問K2プレーヤーが必要です。
• 同様に先に進み、1 ^st を解決します 質問KNプレーヤーが必要です。
• したがって、問題はGP項の合計K + K ² を見つけることになります。 +…+KNは次の値に等しくなります：K（K ⁿ -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