백준 11401번 ( 합동식 )

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

11401번: 이항 계수 3

 

 

우선, 이 문제와 같이 복잡한 식( N!  * [R!(N-R)!] ^ mod-2) % mod )과 같은 경우에는 식을 최소한으로 간결하게 생각할 필

요가 있다. 

N!  * [R!(N-R)!] ^ mod-2) % mod 은 아래와 같이 변형시킬 수가 있다.

1. N! % mod

2.[ R!(N-R)! ^ mod-2] % mod

3. (1 * 2) % mod(최종식)

-> 문제는 2의 식이였다. 위 식을 필자는 아무 생각 없이 곱의 합동식의 성질을 사용하여 식을 막 늘여 버렸다.

그러다 보니, 내가 뭘 하고 있는지 모르겠는 상황이 발생을 했었다.

되도록 간단하게 생각을 해보자. 

R!(N-R)! 을 A라고 치환을 해 보자.

[A^mod-2] % mod  

mod - 2 == 2라고 해 보자.

[A^2] % mod  == ( A % mod ) ^2 % mod 로 변형이 가능하며, 식의 계산이 훨씬 쉬워 진다.

Q. 아래 코드의 문제점은 무엇인가??

unsigned long long result1 = 1;
	for (int x = 1; x <= n;x++) {

		result1 *= x;
		result1 %= mod;
		
	}

A. result *= x; 에서 오버 플로우가 발생할 가능성이 있다.(실제로, 오버 플로우가 발생하여 게속, 틀렸음)( 재귀 함수를 사용하면, 오버 플로우가 발생하지 않게 짤 수가 있다.)

 

Solution : 아래의 코드대로 짜면, 반복문이라도 오버 플로우가 발생하지 않는다. ( 아래 코드를 이해하기 위해서는 약간의 증명이 필요하다. 아래에 증명이 있다.)

B=1;
// R! 구하기
    for(ll i = 1; i <= R; i++){
        B *= i;
        B %= MOD;
    }
    
    // R!(N-R)! 구하기
    for(ll i = 1; i <= N - R; i++){
        B *= i;
        B %= MOD;
    }

 예를 들어,  2! % MOD를 구해보자

1 ] i == 1

B = 1

B = 1 % MOD

2] i == 2

B = (1 % MOD) * 2

B = [ (1 % MOD) * 2 ] % MOD

Q. 과연 [ (1 % MOD) * 2 ] % MOD이 2! % MOD와 동치일까???

증명) 

(1 % MOD)%MOD * 2 % MOD == (1%MOD) * (2 % MOD) == ( 1 * 2 ) % MOD

결론 : 식을 무조건 원자 레벨까지 아무 생각없이 변형시키지는 말자!!!

참고 사이트https://nicotina04.tistory.com/65

페르마의 소정리를 활용한 알고리즘 문제 풀기

https://velog.io/@gidskql6671/%EC%9D%B4%ED%95%AD-%EA%B3%84%EC%88%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98