[BOJ] 4798번: Dirichlet's Theorem

https://www.acmicpc.net/problem/4798

 

슬랙에서 sait2000님이 링크를 올린걸 보고 들어가서 풀어보려고 했습니다. 맨 처음엔 그냥 Miller Rabin 주구장창 돌리면 맞을 수 있는 문제인줄 알았는데 계속 시간초과가 떴고, 양심을 팔고 공식 풀이를 보니 마치 저희가 에라토스테네스의 체를 가지고 소수 판별을 하는 것 처럼 최대 $10^6$개의 후보들에 대해 걸러내는 방식으로 해결을 해야 하는 문제였습니다.

 

방법을 알고 코딩을 했음에도 불구하고 각종 까다로운 예외처리로 인해 굉장히 많이 틀린 후에 맞았네요.

 

https://github.com/blisstoner/BOJ/blob/master/4798.cpp