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