[백준] 11401번 : 이항 계수 3

문제

 

---

풀이

 

페르마의 소정리를 이용해 곱셈의 역원을 구하라던 힌트를 보고 당황했다.

일단 페르마의 소정리가 뭔지 모르겠고, 이항 계수문제랑 곱셈의 역원이 무슨 상관인지도 몰랐기 때문이다.

그래서 힌트를 좀 봤다.

 

 

이항계수를 정리하면 대충 이런 모습인데 우리는 이걸 1,000,000,007로 나눈 나머지를 구해야 한다.

 

그렇다고 이럴 순 없다. 왜냐하면 나머지는 0이 나올 수도 있고, 분모가 0이 되면 안되기 때문이다.

 

그래서 B의 역원을 구한 뒤 그 값에 대해 나머지 연산을 해야한다.

 

그리고 그 역원 계산에 페르마의 소정리가 필요한 것이다.

 

ko.wikipedia.org/wiki/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98_%EC%86%8C%EC%A0%95%EB%A6%AC

페르마의 소정리 - 위키백과, 우리 모두의 백과사전

증명은 필요없고, 2번째 식에 주목해보자.

 

소수 p에 대해 a^(p-1)을 p로 나눈 나머지가 1이라는 것인데, 양변에 a^(-1)을 곱해보도록 하겠다.

a^(p-2)를 p로 나눈 나머지가 바로 a의 역원인 것이다.

 

그럼 우린 저 거듭제곱 연산에 분할정복을 사용하면 되겠다.

---

소스코드

 

#include <iostream>

using namespace std;

typedef long long ll;
const ll DIVISOR = 1000000007;

ll fact(ll num) { //팩토리얼 계산
    ll res = 1;

    for (ll i = 1; i <= num; i++) {
        res *= i;
        res %= DIVISOR;
    }
    return res;
}

ll divide(ll A, ll B) {
    ll tmp;

    if (B == 1) //더이상 나눌 수 없음
        return A % DIVISOR;
    else {
        if (B % 2 == 0) { //짝수 거듭제곱일 때
            tmp = divide(A, B / 2);
            return (tmp * tmp) % DIVISOR;
        } else //홀수 거듭제곱일 때
            return (A * divide(A, B - 1)) % DIVISOR;
    }
}

int main() {
    ll N, K;

    cin >> N >> K;
    ll numerator = fact(N); //분자
    ll denominator = (fact(K) * fact(N - K)) % DIVISOR; //분모
    denominator = divide(denominator, DIVISOR - 2); //페르마의 소정리로 구한 역원
    cout << (numerator * denominator) % DIVISOR;
}

전체 소스코드이다.

 

myunji.tistory.com/255

[백준] 1629번 : 곱셈

거듭제곱을 계산하는 과정은 위 문제의 소스코드와 동일하므로 설명하지 않겠다.

 

ll fact(ll num) { //팩토리얼 계산
    ll res = 1;

    for (ll i = 1; i <= num; i++) {
        res *= i;
        res %= DIVISOR;
    }
    return res;
}

단순한 팩토리얼 계산 함수이다. 다만 숫자가 너무 커지는걸 막기 위해 곱할 때마다 DIVISOR로 나눈 나머지를 취한다.

 

    ll numerator = fact(N); //분자
    ll denominator = (fact(K) * fact(N - K)) % DIVISOR; //분모
    denominator = divide(denominator, DIVISOR - 2); //페르마의 소정리로 구한 역원
    cout << (numerator * denominator) % DIVISOR;

메인 부분이다.

분자에는 따로 할 일이 없고, 분모에 대해서만 divide 함수를 통해 역원을 구한다.