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을 넘어가는 순간부터 결과가 이상해 지더군요.
그냥 배열을 이용해서 계산 하는 방법 밖에 없나요?


ho94949   6년 전

네 이문제에서는 큰 수 연산이 필요합니다. Combination함수가 굉장히 빠르게 증가합니다.

minjun623   6년 전

c언어 에서 제공하는 자료형으로 해결이 불가능 한가요?

ho94949   6년 전

C++ 표준에서 제공하는 자료형으로는 해결할 수 없습니다. 물론 gcc 확장으로 만들어진 적당한 자료형을 사용할 수는 있지만, 큰 수 계산을 구현하는 것을 권장합니다. 사실상 큰 수 계산과 비슷한 일들을 해 주어야 합니다.

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