Problem 245 (改良）

Project Euler C++

C++で書いて，その際，効率の良い方法をつかった．
基本的戦略：
m=q_1q_2\ldots q_l を固定して，
\frac{mp-\phi(m)(p-1)}{mp-1} = 1 / k なるような，pを探す．

そして，semi prime の 場合は q^2 - q + 1 の約数を考えることで， p を求め．
semi prime でない場合は k について考えることで， p を求めた．

で次を利用（探索範囲 2 < n < u)．

  • p < u / m , p < m * m
  • a^2 - a + 1 \equiv b^2 - b + 1 \equiv 0 (mod p) \Longleftrightarrow a \equiv b or 1-b (mod p)
  • k < (m * p_max - 1) / ( (m - phi(m)) * p_max + phi(m))
  • k > (m * q_max - 1) / ( (m - phi(m)) * q_max + phi(m))

C++ のコードは以下から
（パスワードは1