숫자 N이 주어졌을 때, 처음 N개의 팩토리얼(계승)을 모두 곱한 값을 1,000,000,007(109 + 7)로 나눈 나머지를 구하는 것이 이 문제의 목표입니다.
여기서 팩토리얼이란 어떤 수부터 1까지의 모든 자연수를 곱한 것을 의미하며, 느낌표(!) 기호로 표현합니다. 예를 들어 다음과 같습니다.
4! = 4 × 3 × 2 × 1 = 24
즉, 우리는 1!부터 n!까지를 모두 곱한 뒤, 그 결과를 109 + 7로 나눈 나머지를 구해야 합니다.
제약 조건
1 ≤ N ≤ 106
입력 예시 1
n = 9
출력 예시 1
27
설명
1! × 2! × 3! × 4! × 5! × 6! × 7! × 8! × 9! mod (10⁹ + 7) = 27
입력 예시 2
n = 3
출력 예시 2
12
설명
1! × 2! × 3! mod (10⁹ + 7) = 12
문제 해결 접근 방법
- i = 1부터 n까지 반복하면서 각 단계마다 팩토리얼을 계산하고, 그 값들을 누적으로 곱합니다.
- 매번 곱셈 결과를 109 + 7로 나눈 나머지를 저장하여 오버플로우를 방지합니다.
- 최종 결과를 반환합니다.
알고리즘
함수 long long int mulmod(long long int x, long long int y, long long int mod)
Step 1 → result를 0으로 선언 및 초기화
Step 2 → x를 x % mod로 설정
Step 3 → y > 0인 동안 반복
만약 y % 2 == 1이면,
result를 (result + x) % mod로 설정
x를 (x * 2) % mod로 설정
y를 y / 2로 설정
Step 4 → (result % mod) 반환
함수 long long int nfactprod(long long int num)
Step 1 → product와 fact를 1로 선언 및 초기화
Step 2 → MOD를 (10⁹ + 7)로 선언 및 초기화
Step 3 → i = 1부터 i <= num까지 i를 1씩 증가시키며 반복
fact를 mulmod(fact, i, MOD) 호출 결과로 설정
product를 mulmod(product, fact, MOD) 호출 결과로 설정
만약 product == 0이면,
0 반환
Step 4 → product 반환
함수 int main()
Step 1 → num을 3으로 선언 및 초기화
Step 2 → nfactprod(num)을 호출하여 결과 출력
종료예제 코드
#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) {
// y가 홀수일 때 x를 더함
if (y % 2 == 1)
result = (result + x) % mod;
// x에 2를 곱함
x = (x * 2) % mod;
// y를 2로 나눔
y /= 2;
}
return result % mod;
}
long long int nfactprod(long long int num){
// product와 fact를 1로 초기화
long long int product = 1, fact = 1;
long long int MOD = 1e9 + 7;
for (int i = 1; i <= num; i++) {
// 매 반복마다 팩토리얼 계산
fact = mulmod(fact, i, MOD);
// 처음 i개 팩토리얼의 곱
product = mulmod(product, fact, MOD);
// product가 MOD로 나누어떨어지면 0 반환
if (product == 0)
return 0;
}
return product;
}
int main(){
long long int num = 3;
printf("%lld
", (nfactprod(num)));
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
12