体験を伝える―『ガジェット通信』の考え方

面白いものを探しにいこう 本物を体験し体感しよう 会いたい人に会いに行こう 見たことのないものを見に行こう そしてそれをやわらかくみんなに伝えよう [→ガジェ通についてもっと詳しく] [→ガジェット通信フロアについて]

数学の問題をプログラミングで解こう!「LCM・パレード」問題解説

問題のおさらい

自然数 a, b に対し、a と b の最小公倍数を LCM(a, b) と定義します。
例えば、LCM(6, 8)=24 です。

さらに、自然数 n, k に対し、n 以下の全ての自然数 m に対する LCM(k, m)÷k の値の和を F(n, k)と定義します。

例えば F(9, 12)=22 です。以下の表の最下列の数の和です。

数学の問題をプログラミングで解こう!「LCM・パレード」問題解説

同様に、F(10, 3)=43, F(20, 9)=162 となることが確かめられます。

標準入力から、自然数 n と k (1 ≦ n ≦ 108, 1 ≦ k ≦ 105)が半角空白区切りで与えられます。
標準出力に F(n, k) の値を出力するプログラムを書いてください。

方針:等差数列の和に帰着させよう

様々な数について最小公倍数を求める問題です。本問は n の上限が 108 とかなり大きいため、n 以下の一つ一つの数について最小公倍数を求めるコードでは非効率です。うまく高速化する方法を考えましょう。

この問題を解くポイントは、自然数 m を k ごとにグループに区切って考えることです。例えば、k=12 を例にします。1 から始めて、整数 m を 12 ごとにグループ分けしてみましょう。そのときの LCM(12, m)÷12 を書き並べてみます。

数学の問題をプログラミングで解こう!「LCM・パレード」問題解説

各グループの値の和を水色の字で示しています。このグループの値の和が 等差数列 になっていることがポイントです。したがって、等差数列の初項と公差が分かれば、任意のグループまでの和を一発で計算できます。

数式で見てみましょう。j 番目のグループの k 個の値の和は、Σ(シグマ)で次のように書けます。

数学の問題をプログラミングで解こう!「LCM・パレード」問題解説

ここで最小公倍数 LCM を最大公約数(GCD)で書き換えてみます。一般に LCM(x, y)・GCD(x, y) = x・y ですから(下記の Wikipedia の記事を参照して下さい)、次のように書き換えられます。

数学の問題をプログラミングで解こう!「LCM・パレード」問題解説

参考:最小公倍数(Wikipedia)

分母の GCD の部分は、k の倍数の部分を除いても同じ値です。さらに分子の部分を分けて書くと、次のようになります。

数学の問題をプログラミングで解こう!「LCM・パレード」問題解説

最後の緑で囲った部分を P, Q としましょう。これらは i には依存しませんから、つまりこの式は、初項 Q、公差 P の等差数列であることが分かります。グループの個数を c=(n/k の整数部分) とおくと、c 番目のグループまでの値の和は次のようになります。

数学の問題をプログラミングで解こう!「LCM・パレード」問題解説

ここまでくればコーディングが可能です。コード例(Python)は以下です。グループに入らなかった端数の部分を忘れずに計算しましょう。また、LCM や GCD の計算については下記のユークリッドの互除法を用いましょう。

def gcd(x, y):
return gcd(y % x, x) if x > 0 else y

def lcm(x, y):
return x * y / gcd(x, y)

def f(n, k):
c, p, q, r = n/k, 0, 0, 0
for i in range(1, k+1):
p += lcm(i, k) / i
q += lcm(i, k) / k
for i in range(c*k+1, n+1):
r += lcm(i, k)/k
return c*(c-1)*p/2 + c*q + r

n, k = map(int, raw_input().split())
print f(n, k)

参考:最大公約数・最小公倍数・ユークリッドの互除法(外部サイト)

別解:包除原理を活用しよう

別の解き方を紹介します。下のような表を書いてみます。左側は、k=12 に対する上と同じ表です。それに加えて、右側には、12 の約数を並べ、各 m の約数である場合にその商を示しています。この表を見ると、各 m について右端の数字(赤丸)が、LCM(12, m)÷12 の値と一致していることが分かります。

数学の問題をプログラミングで解こう!「LCM・パレード」問題解説

次は表を縦方向に見てみましょう。各約数に対する縦列を見たとき、赤丸がついているのはどんなときでしょうか。それは 12÷(約数)の値が m と互いに素であるときです。そのような値の和をまとめて計算します。包除原理 のテクニックが有用です。例えば、約数が 1 の列の場合、12 と互いに素である n 以下の自然数の和というのは、(全ての和)-(2 の倍数の和)-(3 の倍数の和)+(6 の倍数の和) というように計算します。詳細は下記の記事を参照して下さい。

参考:包除原理(Wikipedia)

コード例は以下です。k の約数それぞれについて、まず約数の一覧を得てから、k/(約数) の素因数の一覧を求め、再帰により k と互いに素である自然数の和を求めています。

# 入力値の約数のリストを得る
def divisors(k):
d, r = 1, []
while d*d

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