밀러-라빈과 폴라드-로 알고리즘을 같이 쓰는 경우가 많아서 간과하는 경우는 많지만, 밀러-라빈 하나만으로도 이미 충분히 쓸모가 있는 알고리즘이다. 그도 그럴 것이, 어떤 수가 소수인지 아닌지 로그 시간만에 판별 가능한 알고리즘이 그렇게 적지는 않다! 밀러-라빈 단독으로 사용하는 대표적인 문제 중 하나가 바로 이 문제이다. 그럼 본격적으로 풀이에 돌입해 보자. 문제 동규부동산에서 아파트를 임대하고 있다. 아파트의 방은 아래 그림과 같이 면적이 2xy+x+y이다. (x와 y는 양의 정수) 동규부동산의 카탈로그에는 아파트의 면적이 오름차순으로 적혀져 있지만, 이 중 일부는 있을 수 없는 크기의 아파트이다. 만약, 이런 크기의 아파트를 임대하겠다고 말하면, 동규는 꽝! 이라고 외치면서, 수수료만 떼어간다. 동규..

사실 이건 제법 쟁여두려고 했으나... 작성자 본인이 처음 푼 플래티넘 V 이상 문제이기도 하고, 며칠 간 고민하다 겨우 푼 문제라 그런가 감회가 새롭기도 하다 게다가 이미 방법론은 다른 경로로 알고 있어서 더욱. 그래서 오늘의 문제로 11402번 문제를 택하기도 했다. 열화판으로 11401번 문제가 있는데, 접근 방식은 아예 다르니 조심하길. 잡설이 길었다! 그럼 본격적으로 풀이에 돌입해 보자. 문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 M으로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N, K와 M이 주어진다. (1 ≤ N ≤ \(10^{18}\), 0 ≤ K ≤ N, 2 ≤ M ≤ 2000, M은 소수) 예제 입력) # 예제 입력 1 5 2..