Solved Problems Today

1. Dirichlet's Theorem on Arithmetic Progressions(☆2) time 1:30

昨日に引き続きここの☆2問題を解く。実は、本日の1問目は2006年度のICPCで解いたことがある。せっかくなので昔と同じアルゴリズムで解き、PKUの正誤判定システムに提出。すると「Time Exceeded」の文字が！なにせそのプログラム、アルゴリズムがO(n!)というとんでもプログラムであったのだ。若さとは恐ろしい(笑)。ちなみに、その時は何の問題もなく正答となった。

そんな先入観のため、他の解法(素数のビットマップテーブルを作成しておいてルックアップを行う)に切り替えるのに、ものすごく時間がかかってしまった。南無三。