実装まずは提出コード(Ruby)から。*$<).reduce(1){|a,(q,r)|a*(q==2?r+1:(r+1)*(r+2)*(r+3)/6)}ほぼワンライナーで、やっている計算は特に複雑なものではありません。ように素因数分解して、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から次のようにして割り出したと考えることもできます。10$$9=2+3+4$$10=1+2+3+4$ということは、次のようなマスの取り方もあるはずです。10$の部分はそのままに、9,10の分解の方法を次の式のように変えたもの、とも言えます。$9=4+5$$10=10$では、ある数$x$に対して、この分解の仕方が何通りあるかを$\phi(x)$で表すことにしましょう。あれば、$9,\,\,4+5,\,\,2+3+4$の3通りがありますから、$\phi(9)=3$となります。この$\phi(x)$を用いると、$F(n)$を次のように表せることが分かります。\phi(x)\phi(y)$さて。この$\phi(x)$の正体はなんでしょうか。ある数に対して、連続する自然数の合計の和がその数になるような取り方が何通りあるか、を表すものです。実は、これは過去の問題「ステップ・アップ・サム」と大きく関係してきます。ange1のブログの「別解」をご覧いただきたいのですが、この分け方はxの奇数の約数と1対1に対応します。$\phi(x)$とは、「$x$の奇数の約数の個数」に他なりません。いうことは、$\phi(x)$自体は、「xを素因数分解して、奇素数の指数にそれぞれ1を足して掛け合わせる」という計算で求めることができます。...ただ、今回は総和計算が出てくるため、いちいちこれをやっていては面倒です。そこで、$n$を素因数分解したときの指数がどう$F(n)$に影響するかを考えてみます。$F(n)$の値に対して10倍の効果がある、ということです。(k+1)(r-k+1)=\frac{(r+1)(r+2)(r+3)}{6}$が出てきます。対する指数$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)$が求められる、という結論が得られました。)「ステップ・アップ・サム」の発展形ともいえる問題でした。...そのときに別解を考えていたおかげで割とスムーズに解けましたが、なかったら結構苦戦していたかもしれません。)月別アーカイブはてなブログをはじめよう!ange1さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。