C++에서 게임에서 승리하는 데 필요한 최소 플레이어

문제 설명

1 <=N <=1000000000 및 1 <=K <=1000000000인 각 질문에 대해 N개의 질문과 K개의 옵션이 주어집니다. 작업은 모든 1 <=i <에 대해 i번째 질문을 시도한 플레이어의 총 수의 합계를 결정하는 것입니다. =k 어쨌든 게임에서 승리합니다. 총 플레이어 수의 합을 최소화하고 109+7 모듈로 출력해야 합니다.

오답 시 플레이어가 제거된다는 점에 유의하세요.

예시

N =5이고 K =2이면 답은 62입니다.

알고리즘

• N ^번째 풀기 질문 K 선수가 필요합니다.
• (N-1) ^번째 풀기 질문 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