[백준 17466번] N! mod P 모듈러 연산 성질

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

17466번: N! mod P (1)

모듈러 연산

1. 특징

A+B % C = ((A % C) + (B % C)) % C
A-B % C = ((A % C) - (B % C)) % C
A*B % C = ((A % C) * (B % C)) % C

2. 이걸 왜 쓰는거죠?

오버 플로우 막으려고!

unsigned long long : 2^64 = 18,446,744,073,709,551,615

그러니 2의 64 제곱까지도 겨우 버티는데
99999988을 다 팩토리얼 연산해서 나중까지 버티다 나머지를 구한다?

이미 오버 플로우 하고도 남았다.

그래서 결과값이 오염되지 않도록 사전에 나머지 연산을 해줘야 (모둘러 연산 특징 사용)
원하는걸 얻을 수 있을것이다.

 

※10^8 = 약 1000ms = 1s

#include <iostream>
using namespace std;

int main()
{
    int N,P; cin >> N >> P; long long res = 1;
    for(int i = 1; i <= N; i++){
        res = ((res * (i % P)))% P;
    }
    printf("%lld", res);
    return 0;
}