2つの配列の間で条件を満たす値の個数を求めるPythonプログラム

問題の概要

2つの整数配列 nums1 と nums2 が与えられたとき、次の2つの条件を同時に満たす値が何個存在するかを求めます。

• 選んだ値は、nums1 のすべての要素の倍数である（つまり nums1 の各要素はその値の約数になる）
• 選んだ値は、nums2 のすべての要素の約数である

例として、nums1 = [3, 9]、nums2 = [27, 81] が入力された場合を考えます。このとき出力は 2 になります。条件を満たすのは 9 と 27 の2つの値だからです。

• 9 mod 3 = 0 ／ 9 mod 9 = 0 → 9 は nums1 の全要素で割り切れる
• 27 mod 9 = 0 ／ 81 mod 9 = 0 → 9 は nums2 の全要素の約数
• 27 mod 3 = 0 ／ 27 mod 9 = 0 ／ 27 mod 27 = 0 → 27 は nums1 の全要素で割り切れる
• 81 mod 27 = 0 → 27 は nums2 の全要素の約数

解き方のアルゴリズム

この問題はシンプルな全探索で解くことができます。手順は以下のとおりです。

1. カウンタ変数 count を 0 で初期化する
2. 候補となる整数 i を 1 から 100 まで順に調べる
3. フラグ flag を True に設定する
4. nums1 の各要素 j について、i mod j が 0 以外なら flag を False にしてループを抜ける
5. flag が True のままなら、nums2 の各要素 k について、k mod i が 0 以外なら flag を False にしてループを抜ける
6. 最後まで flag が True だった場合のみ count を 1 増やす
7. すべての候補を調べ終えたら count を返す

実装例（Python）

実際のコードは次のようになります。

def solve(nums1, nums2):
    count = 0
    for i in range(1, 101):
        flag = True
        # 条件1: nums1 の全要素で割り切れるか
        for j in nums1:
            if i % j != 0:
                flag = False
                break
        # 条件2: nums2 の全要素の約数になれるか
        if flag:
            for k in nums2:
                if k % i != 0:
                    flag = False
                    break
        if flag:
            count += 1
    return count

nums1 = [3, 9]
nums2 = [27, 81]
print(solve(nums1, nums2))

注意： return 文をループの内側に書いてしまうと、最初の候補を見つけた時点で関数が終了してしまい、正しい個数が得られません。return は必ずすべての候補を調べ終えた後に配置しましょう。

入力と出力

入力：

[3, 9], [27, 81]

出力：

2

より効率的な解法：LCM と GCD を活用する

条件を満たす値は、「nums1 全体の最小公倍数（LCM）の倍数」かつ「nums2 全体の最大公約数（GCD）の約数」でなければなりません。この性質を使うと、計算量を大幅に削減できます。

1. L = lcm(nums1)、G = gcd(nums2) を求める
2. G が L で割り切れない場合、答えは 0
3. 割り切れる場合は、G の約数のうち L の倍数になっているものを数えればよい

先ほどの例では L = lcm(3, 9) = 9、G = gcd(27, 81) = 27 となります。27 の約数は 1, 3, 9, 27 で、このうち 9 の倍数は 9 と 27 の2つです。よって答えは 2 となり、全探索と同じ結果が得られます。配列のサイズや値の範囲が大きい場合は、こちらの方法が有効です。