Problem 245 (改良)

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<n<10^11の答えの下10桁,10桁より大きいパスワードをアップローダーが受け付けなかった.)

http://firestorage.jp/download/e8002cb812d750c5414d4280f4714b67629e3327

ちなみに,自分の環境では5秒以下で走る.

More Reading
Newer// Problem 251
Older// Problem 248