글 읽기 - 11401 문제 어케 푸는 거죠????(전문가 분들 도와주세요ㅠㅠ..)

seanrocket17 6년 전 0

곱셈의 역원이 n*k =(이거 합동 기호에요) 1 (mod m)

을 만족하는 k가 modular inverse 고

무슨 페르마의 (소)정리 : a^(p - 1) =(이것두 합동 기호) 1(mod p)

인가 윌슨 정리 (p - 1)! =(요것두 합동 기호) -1(mod p) 인가 이거 둘중에 하나 써서 푸는 문제인것은 알겠는데 정확히 어케 푸는 거죠????

도와주세요 전문가 분들!!!!!!!!!!!!!!!!!!!!!!!!!!!!!제발요!!!!!!!!!!!!!!!!!!!!!!

도와주세요!!!!!!!!!!!!!!!

supercom 6년 전 20

#include <cstdio>
#include <algorithm>
#define P 1000000007LL
typedef long long ll;
using namespace std;
ll fac[4000001], n, k, inv[4000001];//inv[x]의 정의는 x의inverse가 아닌 x!의 inverse
ll power(ll x, ll y) {    //분할 정복을 이용하여 x^y 구하기
    ll ret = 1;
    while (y > 0) {
        if (y % 2) {
            ret *= x;
            ret %= P;
        }
        x *= x;
        x %= P;
        y /= 2;
    }
    return ret;
}
int main() {
    fac[1] = 1;
    for (int i = 2; i <= 4000000; i++)
        fac[i] = (fac[i - 1] * i) % P;            //factorial 전처리
    inv[4000000] = power(fac[4000000], P - 2);    //페르마의 소정리를 이용하여 fac(400만)의 inverse를 구함(이때 분할 정복을 이용하여 logP의 시간에 처리) 
    for (int i = 4000000 - 1; i > 0; i--) 
        inv[i] = (inv[i + 1] * (i + 1)) % P;    //inverse(fac(i))=inverse(fac(i+1))*(i+1)이라는 수식을 이용하여 전처리
    //총 O(N+logP)시간에 전처리를 끝냄 
    //전처리가 끝났기 때문에 어떤 쿼리가 들어와도 상수시간에 이항 계수를 계산 가능
    scanf("%lld%lld", &n, &k);
    if (n == k || !k) {
        puts("1");
        return 0;
    }
    ll r = (fac[n] * inv[n - k]) % P;
    r = (r*inv[k]) % P;
    printf("%lld\n", r);
    return 0;
}

seanrocket17 6년 전 0

근데 문제는 소수 p가 주어지지 않고 1,000,000,007로 나눈 나머지를 구하라고 되어 있는데 혹시 1000000007이 소수여서 그대로 해도 되는 건가요????

seanrocket17 6년 전 0

네 알고 보니 소수가 맞네요!!!!!!!!!감사합니다.

seanrocket17 6년 전 0

근데 제가 실수로 같은 질문을 두개 올렸는데, 같은 질문인데 이 페이지가 아닌 다른 페이지에서도 다른 분이 같은 내용으로 대답을 해주셨어요.

아무튼 두분다 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

11401 문제 어케 푸는 거죠????(전문가 분들 도와주세요ㅠㅠ..)

seanrocket17 6년 전 0

supercom 6년 전 20

seanrocket17 6년 전 0

seanrocket17 6년 전 0

seanrocket17 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말