본인 자바충이라 컴비네이션 다른 사람들 코드 보니깐
보통 빅인티저나 dp뭐시기 해서 풀던데
https://www.acmicpc.net/source/46394025
이사람이 짜놓은게 지리더라구여
조합 nCk 에 대해서
모든 음이 아닌 정수의 n과 k 에 대해서 ( n >= k)
a = a * n / 1;
a = a * n-1 / 2;
...
a = a * n-k+1 / j;
이 단계적으로 진행 될 때,
'a 는 항상 자연수다' 를 증명한 자료 같은게 있나여
그게 nCr이잖아
보통 교육과정에서 배우는게, nCr = n! / r! (n-r)! 이런식으로 배우잖아여
저런 성질은 들어본적이 없는데, 혹시 정수론 같은 제대로된 과목을 배워야 하는 부분인지?
그러니까 저거 차례차례 계산한게 aC0, aC1, ....이렇게 되는거 아님?
아니 nC0, nC1 이렇게
네 그러네영
개신기하네
nC1 nC2 nC3 ... nCk 되는거네 , 그러면 결과는 항상 자연수겠네
n-k+1 ~ n 사이에 k의 배수 하나는 존재함. 증명은 귀류법같은거 쓰면 될듯?
당연히 자연수니까...각 조합값이 - dc App
음 이런증명은 어때 3으로 나눌땐 n, n-1, n-2 이 세개가 곱해져있는 상태니 이 중 3의 배수가 무조건 1개 있다 - dc App
해당 댓글은 삭제되었습니다.
와
저걸로 모자랄걸요 예를들어 1 4 7 9에는 2의 배수가 1개, 4의 배수가 1개 있지만 곱이 2 * 4로 나누어 떨어지지 않음