boj11401번 이항 계수 3

확장 유클리드 호제법을 배워야 한다. 이거 모르고 이 문제 풀면 천재다.

일단 모듈러 연산부터 알아보자. 

 

1.

17 mod 5 = 2 (쉽다.)

 

그러면 

-3 mod 11 은?

3 mod 11 = 3 -> -3(*-1 해줌) + 11 = 8;

-1 mod 11 은?

1 mod 11 = 1 -> -1(*-1 해줌) + 11 = 10

 

만약 a mod b 에서 |a| < |b| 이면

a mod b => a+b mod b 해도 된다.

-3 mod 11 = 8 mod 11 = 8;

 

 

2. 모듈러 연산 속성

(a+b) mod n = ( a mod n + b mod n) mod n

덧셈, 뺄셈, 곱셈에 대해서 이 법칙이 된다. 

 

그러면 이건 알까?

a^b mod n = ( (a mod n)^b) mod n .. 거듭 제곱도 된다.

 

 

3. 모듈러 역수 (어렵다)

 

(13/14) mod 11 은?

 

일단 저 식을 변형하자.

= (13 * 14^-1 ) mod 11

= (13 mod 11 *  (14 mod 11)^-1) mod 11

= (2 * 3^-1) mod 11

 

이때 3^-1 mod 11 와 같은 식을 구할라면   3 * x mod 11 = 1인 x를 찾으면 된다.

왜 1이냐면 3^-1 과 x은 역원 관계이기 때문이다.

그러면 x 는 4, 15, 26, 37이다.

즉 3^-1 mod 11 == 4 mod 11 이다.

 

(2 * 3^-1) mod 11

= (2 * 4) mod 11 = 8인 것이다.

 

Q) (5/3) mod 11은 뭘까?

5 * 3^-1 mod 11

= 5*4 mod 11 = 9

 

 

 

4. 확장 유클리드 알고리즘(대가리 터짐)

확장 유클리드 알고리즘이란

ax + by = c에서 c의 값이 gcd(a, b)의 배수일 때만 정수해를 갖는다고 알려져있다.

따라서 ax + by = c가 정수해를 갖는 c의 최솟값이 gcd(a,b)가 되는 것이다.

이를통해 확장 유클리드 알고리즘은 a, b의 최대 공약수와 ax + by = gcd(a,b)를 만족하는 x, y도 구하는 알고리즘이다.출처: https://www.crocus.co.kr/1232 [Crocus]

 

 

5. 나머지 연산 곱셈의 역수(역원 구하기)

 

13/14 mod 11 은?

(2 * 3^-1) mod 11 이다.

이제 3^-1 mod 11은 무엇일까?

as + bt = gcd(a,b) 에서 a = 11, b = 3을 넣고 확장 식 구하자.

 

s는 -1 t는 4가 나오지 않나?

11*s +3*t = 1

11*s mod 11은 무조건 0이니 3*t는 무조건 1이 나와야 한다.  즉 t값(4)은 3^-1 의 역원이다.

만일 t값이 음수면 t+11(MOD) 를 해준다.

 

 

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

11401번: 이항 계수 3

를 풀어보자.

 

답.

 

 

#include <iostream>
#include <vector>
#define MOD 1000000007
#define ll long long int
using namespace std;
 
 
ll gogo(ll a, ll b)
{
    vector<ll> s, t, r, q;
 
    s.push_back(1); s.push_back(0);
    t.push_back(0); t.push_back(1);
    r.push_back(a); r.push_back(b);
 
    while (1)
    {
 
        ll r2 = r[r.size() - 2];
        ll r1 = r[r.size() - 1];
        q.push_back(r2 / r1);
        r.push_back(r2 % r1);
 
        if (r2%r1 == 0)
        {
            return t[t.size() - 1];
        }
        ll news = s[s.size() - 2] - s[s.size() - 1] * q[q.size() - 1];
        ll newt = t[t.size() - 2] - t[t.size() - 1] * q[q.size() - 1];
 
        s.push_back(news);
        t.push_back(newt);
 
 
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int a, b;
    cin >> a >> b;
 
    if (b == 0)
    {
        cout << 1;
        return 0;
    }
// 일단 a! / (b!*(a-b)!) 를 해주자.
    ll c = 1;
    for (ll i = 1; i <= a; i++)
    {
        c = (c * i) % MOD;
    }
    ll d = 1;
    for (ll i = 1; i <= b; i++)
    {
        d = (d * i) % MOD;
    }
    for (ll i = 1; i <= (a - b); i++)
    {
        d = (d * i) % MOD;
    }
    ll new_d = gogo(MOD, d);
    if (new_d < 0)
        new_d += MOD;
    cout << (c * (new_d)) % MOD;
 
 
}
 

개어렵다. 그런데 페르마의 소정리로 풀면 좀 더 쉽게 풀 수 있다.

 

대충 -> c== 소수 이고 b가 c의 배수가 아니면

(A/B)%C  == (A*B^(C-2)) % C 이다. 천잰가?