資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝研究
法律研究C++ 中前 N 個階乘的乘積
給定一個數 N，任務是求出前 N 個階乘積，模 1000000007。階乘是指小於或等於該數的所有數的乘積，用 !（感嘆號）表示，例如 - 4! = 4x3x2x1 = 24。
因此，我們必須找出 n 個階乘的乘積，並模以 1000000007。
約束
1 ≤ N ≤ 1e6.
輸入
n = 9
輸出
27
說明
1! * 2! * 3! * 4! * 5! * 6! * 7! * 8! * 9! Mod (1e9 + 7) = 27
輸入
n = 3
輸出
12
說明
1! * 2! * 3! mod (1e9 +7) = 12
下面使用的解決問題的思路如下
從 i = 1 遞迴求階乘直到 n，並對所有階乘求乘積
對所有階乘的乘積求模 1e9 +7
返回結果。
演算法
In Fucntion long long int mulmod(long long int x, long long int y, long long int mod) Step 1→ Declare and Initialize result as 0 Step 2→ Set x as x % mod Step 3→ While y > 0 If y % 2 == 1 then, Set result as (result + x) % mod Set x as (x * 2) % mod Set y as y/ 2 Step 4→ return (result % mod) In Function long long int nfactprod(long long int num) Step 1→ Declare and Initialize product with 1 and fact with 1 Step 2→ Declare and Initialize MOD as (1e9 + 7) Step 3→ For i = 1 and i <= num and i++ Set fact as (call function mulmod(fact, i, MOD)) Set product as (call function mulmod(product, fact, MOD)) If product == 0 then, Return 0 Step 4→ Return product In Function int main() Step 1→ Declare and Initialize num = 3 Step 2→ Print the result by calling (nfactprod(num)) Stop
舉例
#include <stdio.h>
long long int mulmod(long long int x, long long int y, long long int mod){
long long int result = 0;
x = x % mod;
while (y > 0) {
// add x where y is odd.
if (y % 2 == 1)
result = (result + x) % mod;
// Multiply x with 2
x = (x * 2) % mod;
// Divide y by 2
y /= 2;
}
return result % mod;
}
long long int nfactprod(long long int num){
// Initialize product and fact with 1
long long int product = 1, fact = 1;
long long int MOD = 1e9 + 7;
for (int i = 1; i <= num; i++) {
// to find factorial for every iteration
fact = mulmod(fact, i, MOD);
// product of first i factorials
product = mulmod(product, fact, MOD);
//when product divisible by MOD return 0
if (product == 0)
return 0;
}
return product;
}
int main(){
long long int num = 3;
printf("%lld \n", (nfactprod(num)));
return 0;
}輸出
如果執行以上程式碼，它將生成以下輸出 -
12
更新時間：13-Aug-2020
304 次瀏覽
廣告