글 읽기 - 어떤 점이 틀린건가요?

vegahouse102 3년 전 0

페르마 소정리를 이용해 풀어봤는데 무엇이 틀렸는지 잘 모르겠습니다.

#include <iostream>

using namespace std;
long long power(long long a, long long b){
    if(b==1)
        return a;
    else{
        long long tmp = power(a,b/2);
        if(b%2)
            return (((tmp*tmp)%1000000007)*a)%1000000007;
        else
            return (tmp*tmp)%1000000007;
    }
}
int main() {
    int n, m;
    long long *arr;
    scanf("%d %d ",&n,&m);
    arr = new long long[n+1];
    arr[0] = 1;
    for(int i = 1; i <= n; i++)
        arr[i] = (arr[i-1]*i)%1000000007;
    printf("%lld",((arr[n])*power(arr[m]*arr[n-m],1000000005))%1000000007);
    delete[] arr;
}

sontg123 3년 전 2

arr[m]*arr[n-m] 가 mod보다 커질 수 있으므로 여기서도 연산 해주셔야 합니다

#include <iostream>
#define INF 1000000007
using namespace std;
long long power(long long a, long long b){
    if(b==1)
        return a;
    else{
        long long tmp = power(a,b/2);
        if(b%2)
            return (((tmp*tmp)%INF)*a)%INF;
        else
            return (tmp*tmp)%INF;
    }
}
int main() {
    int n, m;
    long long *arr;
    scanf("%d %d ",&n,&m);
    arr = new long long[n+1];
    arr[0] = 1;
    for(int i = 1; i <= n; i++)
        arr[i] = (arr[i-1]*i)%INF;
    printf("%lld",((arr[n])*power((arr[m]*arr[n-m])%INF,INF-2))%INF);
    delete[] arr;
}

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

문제

문제

출처

ICPC

어떤 점이 틀린건가요?

vegahouse102 3년 전 0

sontg123 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말