資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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 次檢視
廣告