(1) 실수 오차

(2) 중간 중간에 일어날 수 있는 오버플로우 문제

그런데 사실 (2)로 인해 틀리시진 않으셨을 거고요.

(1) 이 꽤 커보이네요. 예를 들어봅시다. m = 30, n = 15라고 하면..

일단 이렇게 계산이 될 거에요.

30/1 * 29/2 * 28/3 * 27/4 * ...

문제는요. double형으로 28/3을 정확하게 표현하지 못합니다. 약간의 오차가 생깁니다.

그게 누적되었기 때문에 꽤 큰 오차가 생긴 것이지요.

그러면 이걸 어떻게 풀 수 있을까요? m, n이 적당히 작은 경우

2차원 배열을 선언해서 푸실 수 있습니다. 흔히 아시는. nCm = n-1Cm + n-1Cm-1 을 이용해서 푸실 수 있고요. 이 때는

O(n^2) 정도 됩니다.

그게 힘든 경우 에라스토스의 체 + 소인수 분해를 해서 푸실 수 있습니다. 이게 가장 쉬운 방법이고요.

이 때 시간복잡도는 O(n^2)보다는 작습니다.

(1) 일단 1부터 n까지 에라스토스의 체를 이용해서 소수를 걸러내는 것 : O(nlog(logn))

(2) n보다 작은 소수는 대충 n/logn개

(3) a*(a+1)*...*(b-1)*b에 소수 x가 몇 개 있는가? 이건 대충 O(log(x))

복잡도는 (2) + (3)에 의해서 결정될 거 같네요.

진짜로 계산하고 싶으시다면 여기 참고하세요.

https://en.wikipedia.org/wiki/...

약간 도움이 될 지도 모르겠습니다.

결국 DP로 풀어야 하는 건가요? 바로 계산해서 풀어 보고 싶은게 제 생각이라...어려운걸까요..?

저 방식으로 풀려면..

소인수 분해를 하셔야 합니다.

소인수 분해라...

일단 이 문제가 DP이기 때문에 이항계수로 풀면 되겠다 생각하고 풀려고 했습니다.

근데 그냥 계산으로도 될 것 같아서 해봤는데..막혀서 질문을 드렸습니다.

아..근데 소인수 분해를 어떻게 이용해서 풀어야 하는지 감이 잡히지 않습니다...

모든 수를 분해해서 나눠주면서 풀라는 말씀이신가요??

네. 그런데. 이건 n, m이 크지 않으므로

dp로 푸는 게 제일 빠르고 쉬운 방법일 거에요.