「マルチプル・テーブル」問題解答 ( CodeIQ )
はじめに
CodeIQというところでプログラミング問題「マルチプル・テーブル」に解答しましたので、ネタバレです。
問題
次の図にあるような、いわば無限に続く九九の表を考えます。
その時に、入力から与えられる $n$ に対して、表の中から長方形状に合計 $n$ となるマスの取り方が何通りあるか ( これを $F(n)$ とする ) を計算し、出力します。
次の図は $n=9$ の例ですが、マスの取り方が10通りあるため、$F(9)=10$ となります。
解説
実装
まずは提出コード(Ruby)から。
require"prime"
p Prime.prime_division(eval *$<).reduce(1){|a,(q,r)|a*(q==2?r+1:(r+1)*(r+2)*(r+3)/6)}
ほぼワンライナーで、やっている計算は特に複雑なものではありません。 $n=2^{r_0}\cdot 3^{r_1}\cdot 5^{r_2}\cdots$ のように素因数分解して、2の指数$r$に対しては$r+1$を、それ以外の素数の指数$r$に対しては$\frac{(r+1)(r+2)(r+3)}{6}$を計算し、掛け合わせるというものです。
詳細
例えば、次のようなマスの取り方を考えてみます。
この赤い枠で囲った長方形部分の12マスの合計を計算すると90になります。つまり、$n=90$に対するマスの取り方の1例ということです。
…しかし、わざわざ12マス全て1つ1つ足さずとも、次の式で計算できます。
- $(2+3+4)\times(1+2+3+4)=90$
これは分配法則の適用ですね。そう考えると、このマスの取り方はn=90から次のようにして割り出したと考えることもできます。
- $90=9\times 10$
- $9=2+3+4$
- $10=1+2+3+4$
ということは、次のようなマスの取り方もあるはずです。
これは、$90=9\times 10$の部分はそのままに、9,10の分解の方法を次の式のように変えたもの、とも言えます。
- $9=4+5$
- $10=10$
では、ある数$x$に対して、この分解の仕方が何通りあるかを$\phi(x)$で表すことにしましょう。9 であれば、$9,\,\,4+5,\,\,2+3+4$の3通りがありますから、$\phi(9)=3$となります。この$\phi(x)$を用いると、$F(n)$を次のように表せることが分かります。
- $F(n)=\sum_{xy=n} \phi(x)\phi(y)$
さて。では、この$\phi(x)$の正体はなんでしょうか。ある数に対して、連続する自然数の合計の和がその数になるような取り方が何通りあるか、を表すものです。 実は、これは過去の問題「ステップ・アップ・サム」と大きく関係してきます。詳細は、以前の記事「ステップ・アップ・サム」問題解答（CodeIQ） - ange1のブログの「別解」をご覧いただきたいのですが、この分け方はxの奇数の約数と1対1に対応します。すなわち$\phi(x)$とは、「$x$の奇数の約数の個数」に他なりません。
ということは、$\phi(x)$自体は、「xを素因数分解して、奇素数の指数にそれぞれ1を足して掛け合わせる」という計算で求めることができます。
…ただ、今回は総和計算が出てくるため、いちいちこれをやっていては面倒です。そこで、$n$を素因数分解したときの指数がどう$F(n)$に影響するかを考えてみます。
例えば、$n=3^2m$ ( $m$は3の倍数でない ) とします。そうすると、 $$ \begin{eqnarray} F(n)&=&\sum_{xy=n}\phi(x)\phi(y) \\ \,&=&\sum_{xy=m}\phi(3^0x)\phi(3^2y)+\sum_{xy=m}\phi(3^1x)\phi(3^1y)+\sum_{xy=m}\phi(3^2x)\phi(3^0y) \\ \,&=&\sum_{xy=m}1\phi(x)\times 3\phi(y)+\sum_{xy=m}2\phi(x)\times 2\phi(y)+\sum_{xy=m}3\phi(x)\times 1\phi(y) \\ \,&=&10\sum_{xy=m}\phi(x)\phi(y) \\ \,&=&10F(m) \end{eqnarray} $$
つまり、奇素数3に対する指数 2 は、$F(n)$の値に対して10倍の効果がある、ということです。この倍率を一般の奇素数の指数$r$に対して計算すると、
- $\sum_{k=0}^{r} (k+1)(r-k+1)=\frac{(r+1)(r+2)(r+3)}{6}$
が出てきます。
あと残った点として。$n$を素因数分解した場合の、2 に対する指数$r$はどのような影響があるでしょうか?
$\phi(x)$は奇数の約数の個数ですから、2に対する指数は全く影響を与えません。
ですが、$n=xy$と分解する際に、$x,y$それぞれに2の指数をどう割り振るか、その組み合わせの数には影響があります。これは積の分割の仕方だけの話ですから、$r+1$倍として効いてきます。
ということで、trivialに$F(1)=1$であることもあわせると、「2の指数$r$に対しては$r+1$を、それ以外の素数の指数$r$に対しては$\frac{(r+1)(r+2)(r+3)}{6}$を計算し、掛け合わせる」という計算で$F(n)$が求められる、という結論が得られました。
終わりに
以前の ( 1年近く前ですが )「ステップ・アップ・サム」の発展形ともいえる問題でした。…そのときに別解を考えていたおかげで割とスムーズに解けましたが、なかったら結構苦戦していたかもしれません。
