ผลิตภัณฑ์ของ N factorials แรกใน C++

ให้หมายเลข N ภารกิจคือการหาผลคูณของโมดูโล N แฟคทอเรียลแรกโดย 1000000007 . แฟกทอเรียลบอกเป็นนัยเมื่อเราพบผลคูณของตัวเลขทั้งหมดด้านล่างตัวเลขนั้นรวมถึงตัวเลขนั้นด้วย และแสดงด้วย ! (เครื่องหมายอัศเจรีย์) ตัวอย่างเช่น − 4! =4x3x2x1 =24.

ดังนั้นเราต้องหาผลคูณของ n แฟคทอเรียลและโมดูโลให้ได้ 100000007..

ข้อจำกัด

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