「LCM・パレード」問題解答 ( CodeIQ )

CodeIQというところでプログラミング問題「LCM・パレード」に解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 空白区切りで入力される2つの自然数 $n,k\,(1\le n\le 10^8,\,1\le k\le 10^5)$ に対し、$F(n,k)$を計算し、出力する
  • $F(n,k)$ とは、$n$以下の全ての自然数$m$に対して$LCM(m,k)\div k$の値を求め、その和を計算したものである ( なおLCMは最小公倍数を表す )

例えば、$F(9,12)$であれば、それぞれの$m$に対する$LCM(m,k)\div k$の値は次の表の通りとなり、合計して22と分かります。

$m$ 1 2 3 4 5 6 7 8 9
$LCM(m,12)$ 12 12 12 12 60 12 84 24 36 -
$LCM(m,12)\div 12$ 1 1 1 1 5 1 7 2 3 22

解説

まず最小公倍数のままだとやり辛いので、2数の最小公倍数と最大公約数(GCD)の関係を使ってみます。

  • $LCM(x,y)=\frac{xy}{GCD(x,y)}$
  • $\Rightarrow LCM(m,k)\div k=\frac{m}{GCD(m,k)}$

ということは、1~n のそれぞれをGCDで割った総和を求めればいいということで、Rubyなら (1..n).reduce(0){|s,m|s+m/m.gcd(k)} と書けちゃいますね。終わり。
…と、流石にこの時点で終わることはできません。$n$の値の範囲を見るに、ループ繰り返し回数が億行ってしまう可能性もあるわけで、とても処理時間的にが間に合う見込みがありません。

なので、$n$が大きくなっても耐えられるように、GCDの値毎に分類して総和を求めると考えてみましょう。例題にあった$F(9,12)=22$であれば、次のようにまとめることができます。

  • $F(9,12)=(1+5+7)\div 1+2\div 2+(3+9)\div 3+(4+8)\div 4+6\div 6$

ただ、まとめたとは言え、和を計算する部分は$(1+5+7)$のように歯抜けになってしまっていますから、これでは一括で計算というわけには行きません。どうにか巧く対処を考える必要があります。

ここで単純な例、ということで素因数が1種類の$k=3^2=9$で考えてみます。各自然数$m$は次のように分類できるはずです。

  • $m$は3の倍数でない … $m$をそのまま加算
  • $m$は3の倍数だが9の倍数ではない … $\frac{m}{3}$を加算
  • $m$は9の倍数 … $\frac{m}{9}$を加算

$k$の方で上限ができていますから、27の倍数,81の倍数,…と延々考える必要はなく、この3パターンのみです。ここで、歯抜けを解消するために次のように変換してみます。

  • $m$は3の倍数でない … $m$を加算
  • $m$は3の倍数だが9の倍数ではない … $\frac{m}{3}=m-(3-1)\times\frac{m}{3}$を加算
  • $m$は9の倍数 … $\frac{m}{9}=m-(3-1)\times(\frac{m}{3}+\frac{m}{9})$を加算

つまり、下の方の分類になったとしても、それより上の分類で現れる項を保持した形に変換しているわけで、これで歯抜けを解消しようという目論見です。これで実際、$F(100,9)$は次のように歯抜けの無い総和で計算できます。

$$ \begin{eqnarray} F(100,9)&=&1+2+\frac{3}{3}+4+5+\frac{6}{3}+7+8+\frac{9}{9}+10+\cdots+98+\frac{99}{9}+100 \\ &=&1+2+\{3-(3-1)\times\frac{3}{3}\}+4+5+\{6-(3-1)\times\frac{6}{3}\}+7+8+\{9-(3-1)\times(\frac{9}{3}+\frac{9}{9})\} \\ &\,&\,\,+10+\cdots+98+\{99-(3-1)\times(\frac{99}{3}+\frac{99}{9})\}+100 \\ &=&(1+2+3+\cdots+99+100)-(3-1)\times(\frac{3+6+\cdots+99}{3}+\frac{9+18+\cdots+99}{9}) \\ &=&(1+2+3+\cdots+99+100)-(3-1)\times\{(1+2+\cdots+33)+(1+2+\cdots+11)\} \\ \end{eqnarray} $$

なお、ここで出てくる33,11はそれぞれ $33=\lfloor\frac{100}{3}\rfloor,\,11=\lfloor\frac{100}{9}\rfloor$ です。なので、素因数が3以外の場合も、指数が$3^2$でなくて $3^3,3^4,\cdots$ と増えたとしても同じように順々に計算できるはずです。

これで大分見通しが立ちました。最後に残った問題は$k$が複数の素因数を持ちうるということです。…なんですが、まあそんな時には再帰でなんとかなります。きっと。こんな感じで。$F(12,6)$の計算を例に挙げてみます。

$$ \begin{eqnarray} F(12,6)&=&F(12,2)-(3-1)\times F(4,2) \\ &=&(1+2+\cdots+12)-(2-1)\times(1+2+\cdots+6)-(3-1)\times\{(1+2+3+4)-(1+2)\} \\ &=&(1+2+\cdots+12)-(2-1)\times\frac{2+4+\cdots+12}{2}-(3-1)\times(\frac{3+6+9+12}{3}-\frac{6+12}{6}) \\ &=&1+\{2-(2-1)\times\frac{2}{2}\}+\{3-(3-1)\times\frac{3}{3}\} \\ &\,&\,+\{4-(2-1)\times\frac{4}{2}\}+5+\{6-(2-1)\times\frac{6}{2}-(3-1)\times\frac{6}{3}+(3-1)\times(2-1)\times\frac{6}{6}\} \\ &\,&\,+7+\{8-(2-1)\times\frac{8}{2}\}+\{9-(3-1)\times\frac{9}{3}\} \\ &\,&\,+\{10-(2-1)\times\frac{10}{2}\}+11+\{12-(2-1)\times\frac{12}{2}-(3-1)\times\frac{12}{3}+(3-1)\times(2-1)\times\frac{12}{6}\} \\ &=&1+\frac{2}{2}+\frac{3}{3}+\frac{4}{2}+5+\frac{6}{6}+7+\frac{8}{2}+\frac{9}{3}+\frac{10}{2}+11+\frac{12}{6} \end{eqnarray} $$

うん、ほら、なんとかなってます。一応一般的な形で書くと、次のような漸化式になっています。

  • $F(n,p^rk')=F(n,k')-(p-1)\times\{F(\lfloor\frac{n}{p^1}\rfloor,k')+F(\lfloor\frac{n}{p^2}\rfloor,k')+\cdots+F(\lfloor\frac{n}{p^r}\rfloor,k')\}$
    ※ただし、$p$は素数、$k'$は$p$の倍数でないものとする

ということで、このような漸化式の整理から分かる通り、( 総和の範囲に関わる ) $n$は、実は全く計算量に影響がなくて、$k$素因数分解を行うところが支配的であるということになります。ベタに組んでもせいぜい $O(\sqrt{k})$ で済むということです。

では最後に実装です。再帰で考えたので、コードも再帰で実装しても良かったのですが、なんとなくノリが合わなかったので、再帰を解いていく様をループで実装しました。

これは、丁度次の計算例 ( $k=30$ ) のように、項が増えていく様をなぞっています。なので、各項の係数とFの第一引数部分をペアにして管理していれば済むわけです。

$$ \begin{eqnarray} &\,&F(n,30) \\ &=&F(n,15)+(1-2)\times F(\lfloor\frac{n}{2}\rfloor,15) \\ &=&F(n,5)+(1-3)\times F(\lfloor\frac{n}{3}\rfloor,5)+(1-2)\times\{ F(\lfloor\frac{n}{2}\rfloor,5)+(1-3)\times F(\lfloor\frac{n}{6}\rfloor,5) \} \\ &=&F(n,5)+(1-2)\times F(\lfloor\frac{n}{2}\rfloor,5)+(1-3)\times F(\lfloor\frac{n}{3}\rfloor,5)+(1-2)\times(1-3)\times F(\lfloor\frac{n}{6}\rfloor,5) \\ &=&F(n,1)+(1-5)\times F(\lfloor\frac{n}{5}\rfloor,1)+(1-2)\times\{F(\lfloor\frac{n}{2}\rfloor,1)+(1-5)\times F(\lfloor\frac{n}{10}\rfloor,1)\} \\ &\,&\,+(1-3)\times\{F(\lfloor\frac{n}{3},1)+(1-5)\times F(\lfloor\frac{n}{15}\rfloor,1)\}+(1-2)\times(1-3)\times\{F(\lfloor\frac{n}{6},1)+(1-5)\times F(\lfloor\frac{n}{30}\rfloor,1)\} \\ &=&F(n,1)+(1-2)\times F(\lfloor\frac{n}{2}\rfloor,1)+(1-3)\times F(\lfloor\frac{n}{3}\rfloor,1)+(1-2)\times(1-3)\times F(\lfloor\frac{n}{6}\rfloor,1) \\ &\,&\,+(1-5)\times F(\lfloor\frac{n}{5}\rfloor,1)+(1-2)\times(1-5)\times F(\lfloor\frac{n}{10}\rfloor,1) \\ &\,&\,+(1-3)\times(1-5)\times F(\lfloor\frac{n}{15}\rfloor,1)+(1-2)\times(1-3)\times(1-5)\times F(\lfloor\frac{n}{30}\rfloor,1) \end{eqnarray} $$

終わりに

なんというか、素因数の重複する部分の符号が、係数をかける度に反転していく様が、なんというか集合の共通部分を足したり引いたりしていくような感じが…。上手く表現できませんが、これなんか用語ありましたっけ?

そして残念ながら、riverplusさんのCodeIQの出題は、残念ながらこれで最後になるようです。これまで様々面白い問題を有難うございました。