数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告