문제

문제 링크

어떻게 접근할 것인가?

  • (a * b) % m 는 ((a % m) * (b % m)) % m 이다.
  • 그렇다면… (a / b) % m 는 ((a % m) / (b % m)) % m (???)
  • 그럼 그렇지 바로 틀려버렸다…

(a / b) % m 은 무엇인가

이해하려 했지만 구글님이 찾아준 방법을 먼저 설명하자.

페르마의 소정리와 등등의 방법을 도입하다보면 찾을 수 있는 공식…

((a % M)×(b^(M−2) % M)) % M

Pow 계산을 빨리 해주는 효율적으로 해주는 함수

int fastPow(int base, int exp, int mod) {
    int result = 1;
    for (; exp; exp >>= 1, base = (base * base) % mod) {
        if (exp & 1)
            result = (result * base) % mod;
    }

    return result;
}

두개를 모두 더해서 완성된 코드이다.

코드

#include <vector>
#include <cstdio>

using namespace std;

long long fastPow(long long base, long long exp, long long mod) {
    long long result = 1;
    for (; exp; exp >>= 1, base = (base * base) % mod) {
        if (exp & 1)
            result = (result * base) % mod;
    }
    return result;
}

int main() {
    long long n, k;
    scanf("%d %d", &n, &k);
    long long num1 = 1, num2 = 1;
    for(int i = n - k + 1; i <= n; i++) num1 = (num1 * i) % 1000000007;
    for(int i = 1; i <= k; i++) num2 = (num2 * i) % 1000000007;

    printf("%d",(num1 * fastPow(num2, 1000000005, 1000000007)) % 1000000007);
}

느낀점

  • 일단 수학을 완벽하게 이해하지 못한 것이 아쉬웠다.
  • 그래도 페르마의 소정리를 이해하기 위해 알아봤던 여러가지 공식들을 통해 수학을 조금은 알아볼 수 있었던 것 같다:)
  • 일단 다음 문제 고고!!