2407번 - 조합
n, m을 받아서 소인수 분해하여 nCm의 소인수 분해 결과를 구한 이후, 그것들을 곱하는방식으로 코드를 짜 봤는데, unsigned long long 범위를 초과 해 버리네요. (숫자가 필요 이상으로 커지지 않고 결과값보다 항상 작게 하기 위해 소인수 분해를 선택했습니다.)
2 의 갯수는 3개. 여기 까지의 결과는 8
3 의 갯수는 4개. 여기 까지의 결과는 648
5 의 갯수는 0개. 여기 까지의 결과는 648
7 의 갯수는 0개. 여기 까지의 결과는 648
11 의 갯수는 1개. 여기 까지의 결과는 7128
13 의 갯수는 1개. 여기 까지의 결과는 92664
17 의 갯수는 1개. 여기 까지의 결과는 1575288
19 의 갯수는 1개. 여기 까지의 결과는 29930472
23 의 갯수는 0개. 여기 까지의 결과는 29930472
29 의 갯수는 1개. 여기 까지의 결과는 867983688
31 의 갯수는 1개. 여기 까지의 결과는 26907494328
37 의 갯수는 0개. 여기 까지의 결과는 26907494328
41 의 갯수는 0개. 여기 까지의 결과는 26907494328
43 의 갯수는 0개. 여기 까지의 결과는 26907494328
47 의 갯수는 0개. 여기 까지의 결과는 26907494328
53 의 갯수는 1개. 여기 까지의 결과는 1426097199384
59 의 갯수는 1개. 여기 까지의 결과는 84139734763656
61 의 갯수는 1개. 여기 까지의 결과는 5132523820583016
67 의 갯수는 1개. 여기 까지의 결과는 343879095979062072
71 의 갯수는 1개. 여기 까지의 결과는 5968671740803855496
73 의 갯수는 1개. 여기 까지의 결과는 11437923383361764040
79 의 갯수는 1개. 여기 까지의 결과는 18152231747520881592
83 의 갯수는 1개. 여기 까지의 결과는 12448965073759491240
89 의 갯수는 1개. 여기 까지의 결과는 1153247142021623400
97 의 갯수는 1개. 여기 까지의 결과는 1184508333840160104
네 이문제에서는 큰 수 연산이 필요합니다. Combination함수가 굉장히 빠르게 증가합니다.
c언어 에서 제공하는 자료형으로 해결이 불가능 한가요?
C++ 표준에서 제공하는 자료형으로는 해결할 수 없습니다. 물론 gcc 확장으로 만들어진 적당한 자료형을 사용할 수는 있지만, 큰 수 계산을 구현하는 것을 권장합니다. 사실상 큰 수 계산과 비슷한 일들을 해 주어야 합니다.
댓글을 작성하려면 로그인해야 합니다.
minjun623 6년 전
n, m을 받아서 소인수 분해하여 nCm의 소인수 분해 결과를 구한 이후, 그것들을 곱하는방식으로 코드를 짜 봤는데, unsigned long long 범위를 초과 해 버리네요. (숫자가 필요 이상으로 커지지 않고 결과값보다 항상 작게 하기 위해 소인수 분해를 선택했습니다.)
2 의 갯수는 3개. 여기 까지의 결과는 8
3 의 갯수는 4개. 여기 까지의 결과는 648
5 의 갯수는 0개. 여기 까지의 결과는 648
7 의 갯수는 0개. 여기 까지의 결과는 648
11 의 갯수는 1개. 여기 까지의 결과는 7128
13 의 갯수는 1개. 여기 까지의 결과는 92664
17 의 갯수는 1개. 여기 까지의 결과는 1575288
19 의 갯수는 1개. 여기 까지의 결과는 29930472
23 의 갯수는 0개. 여기 까지의 결과는 29930472
29 의 갯수는 1개. 여기 까지의 결과는 867983688
31 의 갯수는 1개. 여기 까지의 결과는 26907494328
37 의 갯수는 0개. 여기 까지의 결과는 26907494328
41 의 갯수는 0개. 여기 까지의 결과는 26907494328
43 의 갯수는 0개. 여기 까지의 결과는 26907494328
47 의 갯수는 0개. 여기 까지의 결과는 26907494328
53 의 갯수는 1개. 여기 까지의 결과는 1426097199384
59 의 갯수는 1개. 여기 까지의 결과는 84139734763656
61 의 갯수는 1개. 여기 까지의 결과는 5132523820583016
67 의 갯수는 1개. 여기 까지의 결과는 343879095979062072
71 의 갯수는 1개. 여기 까지의 결과는 5968671740803855496
73 의 갯수는 1개. 여기 까지의 결과는 11437923383361764040
79 의 갯수는 1개. 여기 까지의 결과는 18152231747520881592
83 의 갯수는 1개. 여기 까지의 결과는 12448965073759491240
89 의 갯수는 1개. 여기 까지의 결과는 1153247142021623400
97 의 갯수는 1개. 여기 까지의 결과는 1184508333840160104
70을 넘어가는 순간부터 결과가 이상해 지더군요.