C++でXとYだけを使って作れる数の個数を数える方法

問題の概要

3つの整数 X、Y、N が与えられます(N は判定対象となる範囲 [1, N] を表します)。この課題のゴールは、1 から N までの数の中に、「X と Y のみを何度でも使って」構成できる数がいくつあるかを求めることです。

例えば X=2、Y=3 の場合を考えてみましょう。6 は「2 を3回足したもの(2+2+2)」でも「3 を2回足したもの(3+3)」でも作れます。同様に 7 は「2 を2回と 3 を1回(2+2+3)」で構成できます。一方で、X と Y の組み合わせではどうしても作れない数も存在します。

この問題は、1 から N までの各数値に対して X または Y を繰り返し引き算していき、最終的にちょうど 0 になればその数を「作れる数」と判断し、カウントを1増やすというシンプルな方針で解くことができます。

入出力例

例1

入力

N=10 X=4, Y=3

出力

Total numbers constructed using X & Y only: 7

説明

3 と 4 だけで作れる数は次の7個です。

3, 4, 6(3+3), 7(3+4), 8(4+4), 9(3+3+3), 10(3+3+4)

例2

入力

N=10 X=5, Y=4

出力

Total numbers constructed using X & Y only: 5

説明

4 と 5 だけで作れる数は次の5個です。

4, 5, 8(4+4), 9(4+5), 10(5+5)

アルゴリズムの考え方

• 3つの整数 X、Y、N を受け取ります。
• 関数 constructNums(int n, int x, int y) は、x と y だけで構成できる数の個数を返します。
• カウント用の変数 count を 0 で初期化します。
• for ループで i = 1 から i <= n まで、範囲内の各数値を順番に調べます。
• 各数値 num = i に対して、while ループで num > 0 の間、以下の処理を繰り返します。
• num が x で割り切れている間(num % x == 0)、num から x を引きます。
• num が y で割り切れている間(num % y == 0)、num から y を引きます。
• x でも y でも割り切れず、かつ num が x と y のどちらよりも大きい場合は、x + y をまとめて引きます。
• 外側の while ループを抜けたときに num が 0 になっていれば、その数は x・y・あるいは両方の組み合わせで作れることを意味するため、count を1増やします。
• すべてのループが終わった時点で、count には条件を満たす数の総数が格納されています。
• count を結果として返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int constructNums(int n,int x,int y){
    int count = 0;
    for (int i = 1; i <= n; i++) {
        int num = i;
        while(num>0){
            while((num%x)==0 && num!=0)
            num-=x;
            while((num%y)==0 && num!=0)
            num-=y;
            if (num>x && num>y)
                num=num-x-y;
            else
                break;
        }
        if (num==0)
            { count++;}
    }
    return count;
}
int main(){
    int N=20;
    int X=5,Y=4;
    cout <<"Total numbers constructed using X & Y only:"<<constructNums(N,X,Y);
    return 0;
}

実行結果

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

Total numbers constructed using X & Y only:14

N=20、X=5、Y=4 の場合、4 と 5 だけで作れる数は 4, 5, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20 の14個となり、結果と一致します。

補足:動的計画法による別解

上記のような引き算ベースのアプローチは直感的で分かりやすい一方、より堅牢に判定したい場合には動的計画法(DP)を利用する方法もあります。dp[0] = true として初期化し、i を 1 から N まで順に走査しながら、「i >= x なら dp[i-x]」「i >= y なら dp[i-y]」のいずれかが true であれば dp[i] = true と更新していきます。最後に dp[1] 〜 dp[N] のうち true の個数を数えれば答えが得られ、計算量は O(N) に抑えられます。