mod 연산 관련 질문
-
게시물 수정 , 삭제는 로그인 필요
저는 외국 코딩 사이트 (codeforces) 에서 활동하다 조합(combination)을 구해야 하는 문제를 보았습니다. (코딩은 컴퓨터 프로그래밍을 통해 수학 문제를 푸는 것입니다)조합을 구하는 공식 (
)은 저도 알고 있지만, 이 문제에서는 n과 r의 범위가 100000 이하로 굉장히 커서 일반적인 공식으로는 답을 구할 수가 없었습니다.
그런데 다른 사람의 풀이를 보니 다음과 같이 구했습니다.
(문제에서는 답이 너무 크기 때문에 조합을 구해 1000000007로 나눈 나머지를 구하라고 했습니다.)
(f(i)=i!, finv(i) = 1/i!, inv()는 finv()를 구하기 위해 필요함)
저는 여기서 정수가 아닌 수에 대해 mod 연산을 하는 것이 가능한지가 궁금했습니다. 또한 inv(i)와 finv(i)를 구하는 공식(점화식)이 어떻게 만들어졌는지도 궁금해졌습니다.
중고등학생 범위에서 최대한 알기 쉽게 설명해주세요.
조합을 구하는 공식 ()은 저도 알고 있지만, 이 문제에서는 n과 r의 범위가 100000 이하로 굉장히 커서 일반적인 공식으로는 답을 구할 수가 없었습니다.
)은 저도 알고 있지만, 이 문제에서는 n과 r의 범위가 100000 이하로 굉장히 커서 일반적인 공식으로는 답을 구할 수가 없었습니다.그런데 다른 사람의 풀이를 보니 다음과 같이 구했습니다.
(문제에서는 답이 너무 크기 때문에 조합을 구해 1000000007로 나눈 나머지를 구하라고 했습니다.)
(f(i)=i!, finv(i) = 1/i!, inv()는 finv()를 구하기 위해 필요함)
저는 여기서 정수가 아닌 수에 대해 mod 연산을 하는 것이 가능한지가 궁금했습니다. 또한 inv(i)와 finv(i)를 구하는 공식(점화식)이 어떻게 만들어졌는지도 궁금해졌습니다.
중고등학생 범위에서 최대한 알기 쉽게 설명해주세요.
#mod 연산 #mod 연산자 #mod 연산 법칙 #mod 연산 분배법칙 #mod 연산 빠르게 #mod 연산 음수 #mod 연산 계산기 #mod 연산 나머지 #mod 연산 방법 #오라클 mod 연산
