Pythonで配列要素の最小公倍数（LCM）がkで割り切れるかどうかを判定する方法

配列 nums と整数 k が与えられたとき、配列内のすべての要素の最小公倍数（LCM）が k で割り切れるかどうかを判定します。

例えば、nums = [12, 15, 10, 75]、k = 10 の場合、配列要素の LCM は 300 となり、300 は 10 で割り切れるため、出力は True になります。

解き方のアプローチ

この問題は次の手順で解くことができます。

• math.gcd を使って、配列の先頭から順に隣接する要素同士の LCM を計算していく
• 最終的に得られた LCM を k で割った余りが 0 かどうかを判定する
• 余りが 0 なら True、そうでなければ False を返す

なお、「どれか1つの要素が k で割り切れればよい」と考えるのは誤りなので注意してください。例えば nums = [2, 3]、k = 6 の場合、個々の要素は 6 で割り切れませんが、LCM は 6 となるため答えは True になります。必ず LCM を計算してから判定しましょう。

実装例

以下のコードで実際の動作を確認できます。

from math import gcd

def solve(nums, k):
    lcm = nums[0]
    for i in range(1, len(nums)):
        lcm = lcm * nums[i] // gcd(lcm, nums[i])
    return lcm % k == 0

nums = [12, 15, 10, 75]
k = 10
print(solve(nums, k))

入力

[12, 15, 10, 75], 10

出力

True

Python 3.9以降ならさらに簡単に書ける

Python 3.9 以降では math.lcm 関数が利用できるため、複数の値の LCM を一度に求められます。次のようにコードを大幅に簡潔化できます。

import math

def solve(nums, k):
    return math.lcm(*nums) % k == 0

まとめ

配列要素の LCM が k で割り切れるかを判定するには、まず LCM を正しく計算し、その余りを確認することが重要です。math.gcd や math.lcm を活用すれば、簡潔かつ効率的に実装できます。個々の要素の割り切り判定だけでは誤った結果になるケースがある点にも留意しましょう。