【C++】((n % i) % j) % n が最大になる (i, j) ペアの個数を求める方法

問題概要

整数 num が入力として与えられます。求めたいのは、((num % i) % j) % num の値が最大になるときのペア (i, j) の個数です。ここで i と j は、どちらも範囲 [1, num] に含まれる整数とします。

入出力例

入力： num = 4
出力： 3
説明： 条件を満たすペアは (3, 2)、(3, 3)、(3, 4) の 3 つです。

入力： num = 6
出力： 4
説明： 条件を満たすペアは (4, 3)、(4, 4)、(4, 5)、(4, 6) の 4 つです。

解法①：ナイーブなアプローチ（全探索）

剰余演算の性質上、ある数 n を「n の半分より少し大きい数」で割ると、余りが最大になります。そこで temp = num / 2 + 1 とおき、最大の剰余を total = num % temp として先に計算しておきます。あとは i と j を 1 から num まで二重ループで全探索し、((num % i) % j) % num が total と一致する組み合わせを数え上げます。

アルゴリズムの手順

• 整数 num を入力として受け取ります。
• 関数 maximized_pair(int num) は、((n % i) % j) % n が最大化される (i, j) ペアの個数を返します。
• カウンタ変数 count を 0 で初期化します。
• 最大剰余を得るため、temp = (num / 2) + 1 とします。
• 最大剰余を total = num % temp として計算します。
• i と j を範囲 [1, num] で二重の for ループにより走査します。
• ((num % i) % j) % num の値が total と一致したら count を 1 増やします。
• すべてのループが終わったら、count を結果として返します。

解法②：効率的なアプローチ（計算量 O(1)）

最大剰余は total = num % temp（temp = num / 2 + 1）で求められることが分かっています。ここでのポイントは、この最大剰余を実現するには i を num に選べばよいという点です。さらに、j を total 以上 num 以下の範囲から選べば、剰余は必ず total になります。したがって、条件を満たすペアの個数は num − total という式一発で求まります。

ただし num = 2 の場合は例外で、4 を返します。このときペアは (1, 1)、(1, 2)、(2, 1)、(2, 2) の 4 つですが、num − total の式では正しく数えられないためです。

アルゴリズムの手順

• 整数 num を入力として受け取ります。
• num == 2 の場合は 4 を返します。
• それ以外の場合は temp = (num / 2) + 1 とし、total = num % temp を計算します。
• count = num − total とします。
• count を結果として返します。

実装例①：ナイーブなアプローチ

#include<bits/stdc++.h>
using namespace std;
int maximized_pair(int num){
    int count = 0;
    int temp = ((num / 2) + 1);
    int total = num % temp;
    for (int i = 1; i <= num; i++){
        for (int j = 1; j <= num; j++){
            int check = ((num % i) % j) % num;
            if (check == total){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int num = 10;
    cout<<"((n % i) % j) % n が最大化される (i, j) ペアの数: "<<maximized_pair(num);
}

出力

((n % i) % j) % n が最大化される (i, j) ペアの数: 6

実装例②：効率的なアプローチ

#include<bits/stdc++.h>
using namespace std;
int maximized_pair(int num){
    int count = 0;
    if (num == 2){
        return 4;
    }
    else{
        int temp = ((num / 2) + 1);
        int total = num % temp;
        count = num - total;
    }
    return count;
}
int main(){
    int num = 10;
    cout<<"((n % i) % j) % n が最大化される (i, j) ペアの数: "<<maximized_pair(num);
}

出力

((n % i) % j) % n が最大化される (i, j) ペアの数: 6

まとめ

ナイーブなアプローチはロジックが直感的で分かりやすい反面、二重ループにより計算量が O(n²) にかかるため、大きな入力には不向きです。一方、効率的なアプローチは「n を n/2 + 1 で割ると余りが最大になる」という剰余演算の性質を利用することで、O(1) で答えを導き出せます。競技プログラミングのように制限時間が厳しい場面では、後者の手法を採用するのが効果的です。