Javaで総利益を最大化するアルゴリズム：LCMを活用した効率的な計算方法

本記事では、5つの整数変数 Num、P1、P2、profit_P1、profit_P2 が与えられたとき、[1, Num] の範囲に含まれる自然数全体から得られる総利益を最大化する問題を解説します。

ルールは以下のとおりです。

• 範囲内のある正の整数が P1 で割り切れる場合、利益は profit_P1 だけ増加します。
• 同様に、その数が P2 で割り切れる場合、利益は profit_P2 だけ増加します。
• ただし、1つの正の整数から得られる利益は最大1回しか加算できません（両方で割り切れる数は、どちらか一方の側でカウントします）。

例で理解しよう

例1

入力： int num = 4, P1 = 6, P2 = 2, profit_P1 = 8, profit_P2 = 2;

出力： 全員の総利益 X = 4

説明： 対象となる数は 1〜4 の範囲 [1, Num(4)] です。

• この範囲に P1（=6）で割り切れる数は存在しません。
• 2 と 4 は P2（=2）で割り切れます。
• したがって利益は 2 × 2 = 4 となります。

例2

入力： int num = 3, P1 = 1, P2 = 2, profit_P1 = 3, profit_P2 = 4;

出力： 全員の総利益 X = 10

説明：

• 1、2、3 はすべて P1（=1）で割り切れます。
• 範囲内で P2（=2）で割り切れるのは 2 のみです。
• つまり 2 は P1 と P2 の両方で割り切れる数です。
• 1 と 3 を P1 でカウントすると、利益は 2 × 3 = 6 になります。
• 2 を P2 でカウントすると、利益は 1 × 4 = 4 になります。
• 2 は両方で割り切れますが、利益を最大化するにはより高い利益が得られる P2 側でカウントします。

合計は 6 + 4 = 10 です。

プログラムのアプローチ

この問題を解くための手順は以下のとおりです。

• 正の数の範囲（Num）、除数 P1 と P2、それぞれに対応する利益 profit_P1 と profit_P2 が与えられます。
• main 関数内で、すべての計算を行うユーティリティメソッド profitMaximisation() を呼び出します。
• P1 と P2 の両方で割り切れる数は、「P1 と P2 の最小公倍数（LCM）の倍数」だけです。二重カウントを避けるため、これらの数はより大きな利益をもたらす側で一度だけカウントします。
• したがって、総利益は次の式で求められます。
  profit_P1 × (num / P1) + profit_P2 × (num / P2) − min(profit_P1, profit_P2) × (num / lcm(P1, P2))
• LCM の計算には、最大公約数（GCD）を再帰的に求める CalculateGcd() メソッドを使用します（lcm(a, b) = a × b / gcd(a, b)）。
• 最終結果は main メソッドで受け取り、ユーザーに出力として表示します。

Java実装例

public class testClass{
    static int CalculateGcd(int n1, int n2){
        if (n2 == 0)
            return n1;
        return CalculateGcd(n2, n1 % n2);
    }
    static int profitMaximisation(int n, int a, int b, int x, int y){
        int result = x * (n / a);
        result += y * (n / b);
        result -= Math.min(x, y) * (n / ((a * b) / CalculateGcd(a, b)));
        return result;
    }
    public static void main(String[] args){
        int num = 6, P1 = 6, P2 = 2, profit_P1 = 8, profit_P2 = 2;
        System.out.println("Maximize the total profit of all the persons X "+profitMaximisation(num, P1, P2, profit_P1, profit_P2));
    }
}

出力

上記のコードを実行すると、以下の出力が得られます。

Maximize the total profit of all the persons X 12

計算内容の確認

この例（num = 6, P1 = 6, P2 = 2, profit_P1 = 8, profit_P2 = 2）の計算過程を見てみましょう。

• P1（=6）で割り切れる数は 6 のみ → 利益 8 × 1 = 8
• P2（=2）で割り切れる数は 2、4、6 の 3つ → 利益 2 × 3 = 6
• しかし 6 は LCM(6, 2) = 6 の倍数であり、両方で割り切れるため二重にカウントされています。そこで小さい方の利益 min(8, 2) = 2 を差し引きます。
• 最終的な総利益は 8 + 6 − 2 = 12 となります。

このように、GCD から LCM を求めて重複分を一度だけ引くことで、O(log N) の高速な計算で総利益の最大値を導き出せます。