sksdong1   5달 전

조금 해보니까

입력 n에 대해 nCr( r=1~n) nCr %M==0 인거 찾으면 답이 될 것 같긴한데

이항계수를 구하자니 N이 100,000이라 너무 크고 해서 어떻게 해야할지 모르겠네요

접근 자체가 틀린건가요??

yukariko   5달 전

이항계수를 다 구할 필요가 없습니다.

M과 관련된것만 필요합니다. 

sksdong1   5달 전

좀더 힌트 주시면 안될까요?

M과 관련됬는지 알려면 이항계수를 알아야 하지 않나요..

yukariko   5달 전

우선 이항계수를 매번 처음부터 구할필요는없습니다.

Big integer가 지원된다고 가정하면 N번의 반복으로 모든 N에 대해 이항계수를 계산할 수 있습니다.

이제 big integer를 구현하지 않기위해서 M을 이용해야합니다.

M을 이용하면 int형을 넘기지않으면서 배수여부를 판단할수있습니다.

다양한 정수론 태크닉이 요구되는 문제네요.

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