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