给定一个数N，求出模100000007的前N个阶乘的乘积。
null
限制条件： 1.≤ N≤ 1e6
例如：
Input : 3Output : 12Explanation: 1! * 2! * 3! = 12 mod (1e9 + 7) = 12Input : 5Output : 34560
先决条件： 模乘 方法： 解决这一问题的基本思想是在这样的大数乘法运算中考虑溢出问题，即阶乘。因此，需要通过递归乘法来克服溢出的困难。此外，在迭代计算阶乘和模乘时，我们必须在每一步取模。
facti = facti-1 * iwhere facti is the factorial of ith numberprodi = prodi-1 * factiwhere prodi is the product of first i factorials
为了求两个大数在模下的乘积，我们使用与 模下的幂运算 …在乘法函数中，我们用+代替*。 以下是上述方法的实施情况。
C++
// CPP Program to find the // product of first N factorials #include <bits/stdc++.h> using namespace std; // To compute (a * b) % MOD long long int mulmod( long long int a, long long int b, long long int mod) { long long int res = 0; // Initialize result a = a % mod; while (b > 0) { // If b is odd, add 'a' to result if (b % 2 == 1) res = (res + a) % mod; // Multiply 'a' with 2 a = (a * 2) % mod; // Divide b by 2 b /= 2; } // Return result return res % mod; } // This function computes factorials and // product by using above function i.e. // modular multiplication long long int findProduct( long long int N) { // Initialize product and fact with 1 long long int product = 1, fact = 1; long long int MOD = 1e9 + 7; for ( int i = 1; i <= N; i++) { // ith factorial fact = mulmod(fact, i, MOD); // product of first i factorials product = mulmod(product, fact, MOD); // If at any iteration, product becomes // divisible by MOD, simply return 0; if (product == 0) return 0; } return product; } // Driver Code to Test above functions int main() { long long int N = 3; cout << findProduct(N) << endl; N = 5; cout << findProduct(N) << endl; return 0; } |
JAVA
// Java Program to find the // product of first N factorials class GFG{ // To compute (a * b) % MOD static double mulmod( long a, long b, long mod) { long res = 0 ; // Initialize result a = a % mod; while (b > 0 ) { // If b is odd, add 'a' to result if (b % 2 == 1 ) res = (res + a) % mod; // Multiply 'a' with 2 a = (a * 2 ) % mod; // Divide b by 2 b /= 2 ; } // Return result return res % mod; } // This function computes factorials and // product by using above function i.e. // modular multiplication static long findProduct( long N) { // Initialize product and fact with 1 long product = 1 , fact = 1 ; long MOD = ( long )(1e9 + 7 ); for ( int i = 1 ; i <= N; i++) { // ith factorial fact = ( long )mulmod(fact, i, MOD); // product of first i factorials product = ( long )mulmod(product, fact, MOD); // If at any iteration, product becomes // divisible by MOD, simply return 0; if (product == 0 ) return 0 ; } return product; } // Driver Code to Test above functions public static void main(String[] args) { long N = 3 ; System.out.println(findProduct(N)); N = 5 ; System.out.println(findProduct(N)); } } // this Code is contributed by mits |
Python3
# Python Program to find the # product of first N factorials # To compute (a * b) % MOD def mulmod(a, b, mod): res = 0 # Initialize result a = a % mod while (b > 0 ): # If b is odd, add 'a' to result if (b % 2 = = 1 ): res = (res + a) % mod # Multiply 'a' with 2 a = (a * 2 ) % mod # Divide b by 2 b / / = 2 # Return result return res % mod # This function computes factorials and # product by using above function i.e. # modular multiplication def findProduct(N): # Initialize product and fact with 1 product = 1 ; fact = 1 MOD = 1e9 + 7 for i in range ( 1 , N + 1 ): # ith factorial fact = mulmod(fact, i, MOD) # product of first i factorials product = mulmod(product, fact, MOD) # If at any iteration, product becomes # divisible by MOD, simply return 0 if not product: return 0 return int (product) # Driver Code to Test above functions N = 3 print (findProduct(N)) N = 5 print (findProduct(N)) # This code is contributed by Ansu Kumari |
C#
// C# Program to find the // product of first N factorials using System; public class GFG{ // To compute (a * b) % MOD static double mulmod( long a, long b, long mod) { long res = 0; // Initialize result a = a % mod; while (b > 0) { // If b is odd, add 'a' to result if (b % 2 == 1) res = (res + a) % mod; // Multiply 'a' with 2 a = (a * 2) % mod; // Divide b by 2 b /= 2; } // Return result return res % mod; } // This function computes factorials and // product by using above function i.e. // modular multiplication static long findProduct( long N) { // Initialize product and fact with 1 long product = 1, fact = 1; long MOD = ( long )(1e9 + 7); for ( int i = 1; i <= N; i++) { // ith factorial fact = ( long )mulmod(fact, i, MOD); // product of first i factorials product = ( long )mulmod(product, fact, MOD); // If at any iteration, product becomes // divisible by MOD, simply return 0; if (product == 0) return 0; } return product; } // Driver Code to Test above functions static public void Main (){ long N = 3; Console.WriteLine(findProduct(N)); N = 5; Console.WriteLine(findProduct(N)); } } //This Code is contributed by ajit. |
PHP
<?php // PHP Program to find the // product of first N factorials // To compute (a * b) % MOD function mulmod( $a , $b , $mod ) { $res = 0; // Initialize result $a = $a % $mod ; while ( $b > 0) { // If b is odd, add 'a' to result if ( $b % 2 == 1) $res = ( $res + $a ) % $mod ; // Multiply 'a' with 2 $a = ( $a * 2) % $mod ; // Divide b by 2 $b /= 2; } // Return result return $res % $mod ; } // This function computes factorials and // product by using above function i.e. // modular multiplication function findProduct( $N ) { // Initialize product and fact with 1 $product = 1; $fact = 1; $MOD = 1000000000; for ( $i = 1; $i <= $N ; $i ++) { // ith factorial $fact = mulmod( $fact , $i , $MOD ); // product of first i factorials $product = mulmod( $product , $fact , $MOD ); // If at any iteration, product becomes // divisible by MOD, simply return 0; if ( $product == 0) return 0; } return $product ; } // Driver Code $N = 3; echo findProduct( $N ), "" ; $N = 5; echo findProduct( $N ), "" ; // This code is contributed by ajit ?> |
Javascript
<script> // Javascript Program to find the // product of first N factorials // To compute (a * b) % MOD function mulmod(a, b, mod) { let res = 0; // Initialize result a = a % mod; while (b > 0) { // If b is odd, add 'a' to result if (b % 2 == 1) res = (res + a) % mod; // Multiply 'a' with 2 a = (a * 2) % mod; // Divide b by 2 b = parseInt(b / 2, 10); } // Return result return res % mod; } // This function computes factorials and // product by using above function i.e. // modular multiplication function findProduct(N) { // Initialize product and fact with 1 let product = 1, fact = 1; let MOD = (1e9 + 7); for (let i = 1; i <= N; i++) { // ith factorial fact = mulmod(fact, i, MOD); // product of first i factorials product = mulmod(product, fact, MOD); // If at any iteration, product becomes // divisible by MOD, simply return 0; if (product == 0) return 0; } return product; } let N = 3; document.write(findProduct(N) + "</br>" ); N = 5; document.write(findProduct(N)); </script> |
输出：
1234560
时间复杂性： O（N*logN），其中O（logN）是模乘的时间复杂度。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
