【C++】nで割り切れるm桁の整数の個数を求める方法

はじめに

2つの整数 m と n が与えられたとき、nで割り切れるm桁の整数の個数を求める問題をC++で解く方法を解説します。

まず、m=1 の場合を考えてみましょう。このとき対象となる数は 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 の10個です。ここで n=3 とすると、3で割り切れる数は 0, 3, 6, 9 の4つとなるため、答えは4になります。

具体例

入力: m=2, n=9
出力: nで割り切れるm桁の数の個数 = 10

解説: 10から99の間で9の倍数となる数は以下の10個です。

18, 27, 36, 45, 54, 63, 72, 81, 90, 99

入力: m=3, n=300
出力: nで割り切れるm桁の数の個数 = 3

解説: 100から999の間で300の倍数となる数は以下の3個です。

300, 600, 900

解法のアプローチ

• 整数 m と n を入力として受け取ります。
• m-1桁の最大の数を num1 として計算します。
• m桁の最大の数を num2 として計算します。
• 関数 findCount(int n, int L, int R) に n と範囲(num1+1 から num2 まで)を渡し、その範囲内で n の倍数となる数をすべて数えます。
• カウントを 0 で初期化します。
• i = L から i = R までループし、i % n == 0 が成立するたびにカウントを1増やします。
• 最終的なカウントを結果として返します。

C++での実装例

#include<bits/stdc++.h>
using namespace std;

// nを約数として持つm桁の数の個数を返す関数
int findCount(int n, int L, int R){
    int count = 0;
    for(int i = L; i <= R; i++){
        if(i % n == 0){
            count++;
        }
    }
    return count;
}

int main(){
    int M = 2, N = 9;
    int i;
    int num1 = 0; // m-1桁の最大の数
    for (i = 0; i < (M - 1); i++)
        num1 = (num1 * 10) + 9;

    int num2 = 0; // m桁の最大の数
    for (i = 0; i < M; i++)
        num2 = (num2 * 10) + 9;

    cout<<"Nの倍数であるM桁の数の個数:"<<findCount(N, num1+1, num2);
    return 0;
}

実行結果

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

Nの倍数であるM桁の数の個数:10

補足: より効率的な計算方法

上記の実装は範囲内のすべての数を1つずつ確認するため、計算量は O(R − L) となります。桁数 m が大きくなると処理に時間がかかるため、実務では次の数式を使うと O(1) で答えを求められます。

個数 = ⌊R / n⌋ − ⌊(L − 1) / n⌋

これは「R以下のnの倍数の個数」から「L−1以下のnの倍数の個数」を引くことで、範囲 [L, R] に含まれるnの倍数の個数を直接計算する方法です。例えば m=2, n=9 の場合は ⌊99/9⌋ − ⌊9/9⌋ = 11 − 1 = 10 となり、先ほどの実行結果と一致します。