C++でKで割った余りがRになる自然数（N以下）の合計を求める方法

問題概要

この問題では、3つの数 N、K、R が与えられます。求めるのは、「N以下の自然数のうち、Kで割った余りがRになる数」の合計です。

具体的には、i % K == R という条件を満たすN以下の数をすべて足し合わせます。

例で理解しよう

入力：

N = 14, K = 4, R = 1

出力：

28

説明： N以下の数のうち、4で割ると1余る数は 1, 5, 9, 13 です。これらを合計すると 1 + 5 + 9 + 13 = 28 となります。

解法のアプローチ

この問題を解くには、R から N まで、K ずつ増加させながらループします。こうすることで、条件を満たす数だけを効率的に取り出し、順に合計へ加算できます。

1ずつ増加させる通常のループでも同じ結果は得られますが、K ずつ増加させるこの方法はループの回数が大幅に減るため、実行時間の短縮につながります。

C++での実装例

解法を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;
int CalcSumofRem(int N, int K, int R){
    int sum = 0;
    for (int i = R; i <= N; i += K) {
        if (i % K == R)
            sum += i;
    }
    return sum;
}
int main(){
    int N = 14, K = 4, R = 1;
    cout<<"Sum of natural numbers (up to "<<N<<") whose modulo with "<<K<<" yields "<<R<<" is "<<CalcSumofRem(N, K, R);
    return 0;
}

出力

Sum of natural numbers (up to 14) whose modulo with 4 yields 1 is 28

このように、ループの開始値を R に設定し、増分を K にすることで、余りの条件チェックを最小限にしながら目的の合計を効率よく求めることができます。