강의실/정보영재

지난번에 페르마의 소정리(https://wondangcom.com/689) 에 대해서 올려 드린 적이 있었는데요.

백준문제중 이항계수3(https://www.acmicpc.net/problem/11401) 이라는 문제를 풀다가 페르마의 소정리를 이용해서 풀이를 하기에 페르마의 소정리를 정리해 보았었습니다.


오늘은 백준문제중 이항계수3 이라는 문제를 페르마의 소정리를 이용해서 어떤 식으로 풀어 나가는지 확인해 보겠습니다.


자연수 n과 k 가 주어졌을때 이항계수를 구하는 문제는 nCk 와 같이 구하면 되고

이것을 식을 이용해 나타내면

n! / (k! * (n-k)! ) 으로 나타낼 수가 있습니다.

하지만 이항계수3 의 문제는 n이 400,000 개의 데이터가 들어 오는데요...

이때 데이터를 모두 계산 후에 1,000,000,0007 으로 나눈 나머지를 출력하라고 하는데요.

문제는 n! / (k! * (n-k)! ) 을 모두 계산 한 후에 1,000,000,0007 으로 나누어야 하는데요.

( 분수 계산은 n! / (k! * (n-k)! ) mod 1,000,000,0007 을 (n! mod 1,000,000,0007) / (k! mod 1,000,000,0007 * (n-k) ! mod 1,000,000,0007) ) 과 같은 형태로 분자 분모에 나누어서 적용하지 못하는 것이 문제가 됩니다.)

그래서 여기서 페르마의 소정리를 이용하게 되는데요.

페르마의 소정리는

a의 (p-1)승 ≡ 1(mod p)

이라는 공식을 이용하는 것입니다.

즉 우리가 구하는 공식을 a = n! , b = k! *(n-k)! 으로 놓는 다고 하면

(a/b) % 1,000,000,0007 이 되며 이것을 다시 표현하면 a * b(-1 승) % 1,000,000,0007 과 같이 표현이 가능합니다.

여기에서 다음과 같은 공식은 성립하지 않습니다.

a % 1,000,000,0007  * b(-1승) % 1,000,000,0007 

b(-1승) 이 분수이기 때문입니다.

따라서 페르마의 소정리를 이용하면

a(p-1 승)≡ 1(mod p)  이므로

a * b(-1 승) % p (여기에서 p는  1,000,000,0007) 을 구하면 됨으로 다음과 같이 식을 변형합니다.

=> a * b(-1승) * 1 % p

=> a * b(-1승) * b(p-1 승) % p

=> a * b(p-2 승) % p 와  같이 표현 가능하고요.

이것은 결국 다음과 같이 계산이 가능합니다.

=> (a % p) * (b(p-2승) %p) % p

(여기서 b(p-2승) 은 분수가 아니기 때문에 곱에서는 mod 의 분배법칙이 성립되기 때문입니다.)


이것을 소스로 구현해 보면 다음과  같습니다.

 

#include <iostream>

using namespace std;

#define P 1000000007LL

long long fac[4000001];

int main()

{

    int n,k;

    cin >> n >> k;

    fac[0]=1;

    fac[1]=1;

    //factorial 구하기

    for(int i=2; i<=n;i++) fac[i] = (fac[i-1] * i) % P;

    //(a%P * b(p-2승) % P) % P 를 구하면 된다.

    long long bVal = (fac[k]*fac[n-k]) % P;

    int index = P-2;

    //b(P-2승) 값을 구하자.

    long long resVal = 1;

    while(index > 0)

    {

        if(index % 2) //인덱스 값이 홀수이면 index

        {

            resVal *= bVal;  //index 값이 홀수이면 bVal을 한번 곱해주자.

            resVal %= P;

        }

        bVal = bVal * bVal;

        //bVal 값을 제곱승 한다.

        //2의 10승인 경우를 계산하면  (2 * 2) * (2 * 2) 를 하게 되면 2의 4승이 되는 원리를 이용한다.

        bVal %= P;

        index /= 2;

    }

    cout << ((fac[n] % P) * (resVal % P)) % P << endl;

    return 0;

}



이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
7 0
  • 핑구야 날자 2019.01.26 07:11    

    이항계수 정말 어려운데 쉽게 풀이 해 주셔서 학생들이 도움이 되겠네요

  • 공수래공수거 2019.01.26 08:25 신고    

    어려운 내용이네요.
    모르는 학생들에게는 도움이 되겠습니다.
    '

  • 휴식같은 친구 2019.01.26 10:38 신고    

    복잡한 수학문제도 코딩이면 간단하게 해결되는듯 합니다.
    즐거운 주말 보내세요~^^

  • 버블프라이스 2019.01.26 14:30 신고    

    저는 어려워서 이해하기가 어렵지만
    코딩하시는 분들에게 좋은 참고 자료가 될 것 같습니다^^
    좋은 주말 보내시길 바래요

  • 행복사냥이 2019.01.26 23:34 신고    

    헉..어렵습니다.ㅎ 행복한 주말 보내세요. ^^

  • 핑구야 날자 2019.01.27 07:16    

    어제에 이어 이항계수에 대해서 잘 알고 갑니다 즐거운 주말 보내세요

  • 청결원 2019.01.27 08:04 신고    

    포스팅 잘 보고 갑니다
    남은 주말 휴일 잘 보내세요