1을 타패하고 33을 또이쯔로 쓰겠다. 며칠 전 대회인 제4회 MatKor의 H번 문제이다. 총 16문제짜리 셋이었으니, 이 뒤로 이것보다 어려운 문제가 8개나 있다는 뜻이다. 이 문제 난이도도 절대 만만하지 않다! 본대회에서 식 정리하는 데만 20분을 넘게 썼다. 내 영역이라서 그나마 빠르게 풀기는 했는데, 그 빠르게 푼다는 게 40분 조금 넘게 걸렸던 문제다. 쏟은 시간 보고 제법 만만치 않으리라고 생각했는데 설마 Platinum I이었을 줄은... 그럼 본격적으로 풀이에 돌입해 보자. 문제 2024년 3월 9일 제4회 MatKor Cup이 개최된다. 이번 MatKor Cup에는 총 \(n\)명이 참가했고, 각 참가자는 \(1\)번부터 \(n\)번까지의 번호가 붙어있다. 이번 대회 운영진인 준혁이는 ..

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