एक संख्या N दी गई है, कार्य पहले N फैक्टोरियल का गुणनफल 1000000007 से मोड्यूलो करके निकालना है। फैक्टोरियल का तात्पर्य है जब हम उस संख्या से नीचे की सभी संख्याओं का गुणनफल निकालते हैं जिसमें वह संख्या भी शामिल होती है और इसे ! (विस्मयादिबोधक चिह्न) से दर्शाया जाता है, उदाहरण के लिए: 4! = 4×3×2×1 = 24।
इसलिए, हमें n फैक्टोरियल का गुणनफल निकालना है और 1000000007 से मोड्यूलो करना है।
बाधा
1 ≤ N ≤ 1e6
इनपुट
n = 3
आउटपुट
12
व्याख्या
1! * 2! * 3! mod (1e9 + 7) = 12
इनपुट
n = 4
आउटपुट
288
व्याख्या
1! * 2! * 3! * 4! mod (1e9 + 7) = 288
समस्या को हल करने के लिए नीचे दिया गया दृष्टिकोण
- i = 1 से n तक पुनरावर्ती रूप से फैक्टोरियल खोजें और सभी फैक्टोरियल का गुणनफल करें
- सभी फैक्टोरियल के गुणनफल को 1e9 + 7 से मोड्यूलो करें
- परिणाम रिटर्न करें।
एल्गोरिदम
In Function long long mulmod(long long x, long long y, long long mod)
Step 1→ result को 0 के रूप में घोषित और इनिशियलाइज़ करें
Step 2→ x को x % mod सेट करें
Step 3→ While y > 0
यदि y % 2 == 1 तो,
result को (result + x) % mod सेट करें
x को (x * 2) % mod सेट करें
y को y / 2 सेट करें
Step 4→ return (result % mod)
In Function long long nfactprod(long long num)
Step 1→ product को 1 और fact को 1 के साथ इनिशियलाइज़ करें
Step 2→ MOD को (1e9 + 7) के रूप में घोषित और इनिशियलाइज़ करें
Step 3→ i = 1 से i <= num तक, i++
fact को (mulmod(fact, i, MOD) फंक्शन कॉल) सेट करें
product को (mulmod(product, fact, MOD) फंक्शन कॉल) सेट करें
यदि product == 0 तो,
0 रिटर्न करें
Step 4→ product रिटर्न करें
In Function int main()
Step 1→ num = 3 घोषित और इनिशियलाइज़ करें
Step 2→ nfactprod(num) कॉल करके परिणाम प्रिंट करें
Stop
उदाहरण
#include <iostream>
using namespace std;
const long long MOD = 1000000007LL;
long long mulmod(long long x, long long y, long long mod) {
long long result = 0;
x = x % mod;
while (y > 0) {
// जहां y विषम है वहां x जोड़ें
if (y % 2 == 1)
result = (result + x) % mod;
// x को 2 से गुणा करें
x = (x * 2) % mod;
// y को 2 से विभाजित करें
y /= 2;
}
return result % mod;
}
long long nfactprod(long long num) {
// product और fact को 1 से इनिशियलाइज़ करें
long long product = 1, fact = 1;
for (int i = 1; i <= num; i++) {
// हर पुनरावृत्ति के लिए फैक्टोरियल खोजने के लिए
fact = mulmod(fact, i, MOD);
// पहले i फैक्टोरियल का गुणनफल
product = mulmod(product, fact, MOD);
// जब product MOD से विभाज्य हो तो 0 रिटर्न करें
if (product == 0)
return 0;
}
return product;
}
int main() {
long long num = 3;
cout << nfactprod(num) << endl;
return 0;
}
आउटपुट
12
