本稿はCodeIQで2014年7月7日～同年7月28日に出題された「七夕問題☆牽牛彦星牛をもっと飼う」という問題の解法に関する記事です。

七夕問題☆牽牛彦星牛をもっと飼う【解説1】

◆基本的な考え方

本問は、格子点（タテ・ヨコの座標が整数に限定される平面上）の問題ということで、エサが無事に届くかどうかは、xy平面上の各点について、x座標とy座標が互いに素である（x座標・y座標共に割り切れる、共通の素数が無い）かどうかで判定することができます。

図は、7×7のサイズの解で○の部分が牛を配置するところになります。格子のサイズが大きくなっても、彦星の場所（黄色い○の部分）の上と右は必ず牛を配置し、それ以降は配置できません。

つまり、下端・左端については計算する必要がありませんので、実際には6×6の格子部分で調べればよいことになります。7777777×7777777のサイズなら、7777776×7777776のサイズで調べます。

また、（左下から右上にかけての）対角線について、○の位置が対称になっています。つまり、調べる点は実際の半分程度で済みます。

調べる量を全体の半分程度として、素であるかどうかは、ユークリッドの互除法を使う等すれば、小さいサイズの問題は難なく解答できるはずです。しかし、この考え方で大きなサイズの問題を解こうとすると、困ったことが起こります。各x座標とy座標について、互いに素であるかどうかを調べるためには、大量の除算が必要になるからです。

この方法のまま解を得るには、ある程度高速に実行できるコンパイラ言語で記述し、さらに並列化等の工夫が必要になります。

◆互いに素な値を簡単に数える方法（その１）

平面上の点について調べますが、実際にプログラムを書く場合は、1列ずつ調べていくことになります。 y座標が1の点は(1, 1)のみ、y座標が2の点は(1, 2), (2, 2)、y座標が3の点は(1, 3), (2, 3), (3, 3)のように、順に見ていくことになります。

具体的な値で考えてみましょう。たとえばy座標が6の場合、 (1, 6), (2, 6), (3, 6), (4, 6), (5, 6), (6, 6)の6つの点に関して、x座標・y座標が互いに素であるのは、 (1, 6)と(5, 6)の2つだけです。

y座標は6で偶数ですので、x座標が偶数になっている部分は、明らかにダメだとわかります。つまり、y座標が偶数なら、x座標とy座標が互いに素かもしれない候補は、半分に絞ることができます。

(1, 6), (3, 6), (5, 6)

このうち、(3, 6)は互いに3で割り切れますから排除し、(1, 6)と(5, 6)の2つだけが残ります。

もう少し大きな値で考えてみましょう。 (1, 60), (2, 60), …, (60, 60)のように、y座標が60のときでも、同じように考えてみると、まずx座標が偶数のものを省くことができます。

(1, 60), (3, 60), (5, 60), (7, 60), (9, 60), (11, 60), (13, 60), (15, 60), …, (59, 60)

ここで、(3, 60)に着目します。この点は、各座標が3で割り切れますので、候補から省くことができますが、この点から3つおきに見ていくと、(9, 60)や(15, 60)も、やはり各座標が3で割り切れます。つまり、全体の1/3を省くことができることになります。

ここまでで、60から半分の30個、30個からその1/3を取り除いた（つまり30個のうちの2/3の）20個と、かなり絞り込むことができました。このうち、x座標が5の倍数になっているものは、次の4つ

(5, 60), (25, 60), (35, 60), (55, 60)

の4種類あります。同じ幅で出現しなくなってしまいましたが、20個のうちの1/5である4個が見つかりました。残りの候補は、

(1, 60), (7, 60), (11, 60), (13, 60), (17, 60), (19, 60), (23, 60), (29, 60), (31, 60), (37, 60), (41, 60), (43, 60), (47, 60), (49, 60), (53, 60), (59, 60)

の16個になりました。そして、これらはすべてx座標とy座標が互いに素になっています。実際に行った計算は、

60 * 1/2 * 2/3 * 4/5 = 16

ですが、2, 3, 5という数字は、60の素因数です。つまり、その数の素因数がすべてわかれば、各点を調べなくても計算で個数がわかるということになります。この計算方法は、オイラーのトーシェント関数とか、φ（ファイ）関数と呼ばれています。具体例で示した値を使うと、φ(6) = 2, φ(60) = 16のように書きます。

解を得るための計算は、

φ(1) + φ(2) + φ(3) + ... + φ(7777776)

を計算することと考えることができます。ここまで工夫できると、速度的に厳しい言語でも、なんとか解を得ることができます。

◆計算量を落とす

1列ごとに計算しますので、1, 2, 3, …, 7777776と、かなりの数について素因数分解が必要になります。前処理として、素数のリストを作っておき、試し割りを行ってもよいのですが、もう少し除算回数を抑えたいところです。

そのために、エラトステネスの篩の要領で、1つ素数pが見つかるごとに、その素数が因数になっている値（つまりその素数の倍数）に対して、(p-1)/pを掛けていくようにしておきます。

[ 1, 2, 3, 4, 5, 6, 7, 8, 9, ..., 7777776 ]

という配列に対して、「2」の部分から、2つ飛びに1/2を掛けます。

[ 1, 1, 3, 2, 5, 3, 7, 4, 9, ..., 3888888 ]

次に、「3」の部分から3つ飛びに2/3を掛けていきます。

[ 1, 1, 2, 2, 5, 2, 7, 4, 6, ..., 2592592 ]

5, 7, 11, 13, …の倍数についても同様の計算を行い、すべて終了した時点ですべての要素を合計すると、正解が得られます。

この方法をRubyで実装すると、簡単なコードですが数秒で解を得ることができます。

require 'prime'

n = 7777777

v = (0..n-1).map.to_a

Prime.take_while {|k| k <= n-1 }.map {|k|
  (k..n-1).step(k) {|i|
    v[i] = v[i] * (k-1) / k
  }
}

puts v.inject {|s,k| s += k } * 2 + 1