[Silver V] 31378 매우 어려운 문제 - 31738

[문제 위치]

https://www.acmicpc.net/problem/31738

[문제 풀이]

이 문제는 수학(모듈러 연산) 를 통해 해결하는 문제이다.
N!을 M으로 나눈 나머지를 구하는 문제이고 N ≥ M이면 N!에 M이 인수로 포함되므로 결과가 0이 되므로, N < M인 경우 곱셈마다 모듈러를 적용해서 선형 시간에 계산한다
아래는 이를 구현한 코드이다.

#include <iostream>
using namespace std;

#define FAST ios::sync_with_stdio(false); cin.tie(nullptr);

int main() {
    FAST;
    long long N, M;
    if (!(cin >> N >> M)) return 0;

    if (N >= M) {                 // N!에 M이 반드시 포함되므로 나머지는 0
        cout << 0 << '\n';
        return 0;
    }

    long long ans = 1 % M;        // N < M 이므로 i % M == i 이지만 형태상 남겨둠
    for (long long i = 2; i <= N; ++i) {
        ans = (ans * i) % M;
    }
    cout << ans << '\n';
    return 0;
}