समस्या विवरण
N प्रश्न और प्रत्येक प्रश्न के लिए K विकल्प दिए गए हैं, जहां 1 ≤ N ≤ 1000000000 और 1 ≤ K ≤ 1000000000। कार्य 1 ≤ i ≤ k के लिए सभी ith प्रश्न का प्रयास करने वाले खिलाड़ियों की कुल संख्या का योग निर्धारित करना है ताकि किसी भी तरह गेम जीता जा सके। आपको खिलाड़ियों की कुल संख्या के योग को न्यूनतम करना होगा और इसे 10^9+7 मॉड्यूलो आउटपुट करना होगा।
कृपया ध्यान दें कि कोई भी गलत उत्तर खिलाड़ी के एलिमिनेशन की ओर ले जाता है।
उदाहरण
यदि N = 5 और K = 2 तो उत्तर 62 है।
एल्गोरिदम
- N-वें प्रश्न को हल करने के लिए K खिलाड़ियों की आवश्यकता होती है।
- (N-1)-वें प्रश्न को हल करने के लिए K² खिलाड़ियों की आवश्यकता होती है।
- इसी तरह आगे बढ़ते हुए, 1-वें प्रश्न को हल करने के लिए K^N खिलाड़ियों की आवश्यकता होती है।
- इसलिए, हमारी समस्या GP पदों K + K² + ... + K^N का योग ढूंढने तक सीमित हो जाती है जो बराबर है: K(K^n - 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
