ガジェット通信

見たことのないものを見に行こう

数学の問題をプログラミングで解こう!「マルチプル・テーブル」問題解説

DATE:
  • ガジェット通信を≫

問題のおさらい

下図のようなかけ算表を考えます。

左上のマスを起点に、右と下にマスがどこまでも続いています。
上から i 行目、左から j 列目のマスには、 i×j の値が書き込まれています。

ここに、罫線に沿った四角形で数字を囲います。
自然数 n に対し、囲われた中の数字の和が n に等しくなるような囲い方の数を F(n) と定義します。

例えば、F(9) = 10 です。題意を満たす囲い方は下記の 10 通りです。
なお、ある囲い方が別の囲い方と部分的に重なっていてもかまいません。
(重なりを見やすくするため、下図では複数の色を使って表しています)

同様に、F(15) = 16、F(25) = 10 となることが確かめられます。

標準入力から、自然数 n(1 ≦ n ≦ 104)が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

方針

ある四角形を変数で定義し、その変数を使って、囲われた数字の和を表してみましょう。

ここでは、4 つの変数 x, y, w, h で四角形を定義します。四角形の左上角のマスを左から x 行目、上から y 列目のマスとします(1 ≦ x, y)。四角形の横の長さを w、縦の長さを h とします(1 ≦ w, h)。

次に、x, y, w, h を使って、囲われた数字の和を表してみましょう。これには、和のΣ(シグマ)を用いた計算を行います。正の整数 i, j を用いて、四角形の中の一つのマスを、左端から i 列目、上端から j 行目のマスと表しましょう。このマスは、表全体では左から x+i-1 列目、上から y+j-1 行目です。よって値として(x+i-1)・(y+j-1)が書き込まれています。また、i, j の範囲は、それぞれ 1 ≦ i ≦ w、1 ≦ j ≦ h です。したがって、この範囲での値の和は次のようになります。

これを計算します。

さて、この値が n に等しくなるわけです。イコール n でつなぎ、1/4 を移項すると、次のようになります。

つまり本問は、上式を満たす正の整数 (x, y, w, h) の組が全部でいくつあるかを求める問題だということです。

実装

そのような組はどのように見つければよいでしょうか。ここで上式をじっと見ましょう。左辺が 4 つの項の積になっています。

そこで、4n を 4 つの整数の積として分解するやり方を列挙しましょう。そしてその 4 つの整数がそれぞれ w, h, 2x+w-1, 2y+h-1 に等しいとしたときの (x, y, w, h) が、題意を満たし得るということです。

4n を 4 つの整数の積に分解するコードには、様々な書き方があります。ここでは一つの書き方として、始めに 4n の約数のリストを作成して、次にこのリストに対する多重ループで 4 つの整数の候補を挙げます。この 4 つの整数を順に w, h, 2x+w-1, 2y+h-1 としたときの x, y がどちらも正の整数になるかどうかをチェックしましょう。

コード例は以下です。

n = int(input())
m = 4 * n
# mの約数のリストを作る
v = []
d = 1
while True:
if d * d > m: break
if m % d == 0:
v.append(d)
if d * d != m: v.append(m / d)
d += 1

answer = 0
# 積が4nとなる4変数w,h,p,qを列挙
for w in v:
for h in v:
for p in v:
if m % (w * h * p) != 0: continue
q = m / (w * h * p)
if q == 0: continue
# xの値が正の整数かどうかチェック
if (p – h + 1) % 2 != 0: continue
x = (p – h + 1) / 2
if x

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

TOP