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桁より大きいパスワードをアップローダーが受け付けなかった．）

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

コンテンツ