Cho một số N, nhiệm vụ là tìm tích của N giai thừa đầu tiên theo môđun của 1000000007. Giai thừa ngụ ý khi chúng ta tìm thấy tích của tất cả các số bên dưới số đó bao gồm cả số đó và được ký hiệu là! (Dấu chấm than), Ví dụ - 4! =4x3x2x1 =24.
Vì vậy, chúng ta phải tìm một tích của n thừa số và môđun bằng 1000000007 ..
Ràng buộc
1 ≤ N ≤ 1e6.
Đầu vào
n = 9
Đầu ra
27
Giải thích
1! * 2! * 3! * 4! * 5! * 6! * 7! * 8! * 9! Mod (1e9 + 7) = 27
Đầu vào
n = 3
Đầu ra
12
Giải thích
1! * 2! * 3! mod (1e9 +7) = 12
Phương pháp được sử dụng dưới đây như sau để giải quyết vấn đề
-
Tìm đệ quy giai thừa từ i =1 đến n và tích tất cả các giai thừa
-
Sửa đổi tích của tất cả các giai thừa bằng 1e9 +7
-
Trả lại kết quả.
Thuật toán
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
Ví dụ
#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; }
Đầu ra
Nếu chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
12