C++でA % X = BとなるXの取り得るすべての値の個数を求める

問題概要

2つの整数AとBが与えられ、「A % X = B」を満たすような整数Xの取り得る値の個数を求めるのが目標です。この条件式については、AとBの大小関係によって次のように場合分けができます。

• A == B の場合：Xは無限に多くの値を取り得るため、-1を返します。
• A < B の場合：解が1つも存在しないため、0を返します。
• A > B の場合：(A − B) の約数のうちBより大きいものの個数を結果として返します。

考え方のポイント

剰余演算の性質上、「余りは必ず割る数よりも小さくなる」ため、A % X = B が成り立つには X > B であることが必要です。また、A % X = B が成り立つとき、A は A = q × X + B（qは整数）の形で表せるため、(A − B) がXで割り切れることも必要です。したがって、求めるべきXの候補は「(A − B) の約数のうちBより大きいもの」ということになります。

入出力例

例1

入力：

A=5, B=2

出力：

A % X = B となるXのすべての可能な値の個数：1

説明：

5 % 3 = 2 なので、このときのXは3です。

例2

入力：

A=10, B=10

出力：

A % X = B となるXのすべての可能な値の個数：-1

説明：

A == B なので解は無限に存在し、-1が返されます。

アルゴリズム・アプローチ

このアプローチでは、forループを i = 1 から i * i <= (A − B) の範囲で回しながら (A − B) の約数を求めます。i が (A − B) を割り切る場合は、count を適宜更新していきます。手順は以下のとおりです。

• 整数AとBを入力として受け取ります。
• A < B の場合は、結果として0を出力します。
• A == B の場合は、結果として-1を出力します。
• A > B の場合は、関数 possible_values(int A, int B) がAとBを受け取り、A % X = B を満たすXのすべての可能な値の個数を返します。
• count の初期値を0、X = A − B とします。
• i = 1 から i * i <= (A − B) までforループで走査し、Xの約数を調べます。
• i がXを割り切る場合、temp = i、temp_2 = B − 1 とし、i * i != X であれば temp_2 = X / i とします。
• temp > B であれば count をインクリメントし、同様に temp_2 > B であっても count をインクリメントします。
• ループ終了後、count を結果として返します。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
int possible_values(int A, int B){
    int count = 0;
    int X = A - B;
    for (int i = 1; i * i <= A - B; i++){
        if(X % i == 0){
            int temp = i;
            int temp_2 = B - 1;
            if(i * i != X){
                temp_2 = X / i;
            }
            if(temp > B){
                count++;
            }
            if(temp_2 > B){
                count++;
            }
        }
    }
    return count;
}
int main(){
    int A = 15, B = 5;
    if(A < B){
        cout<<"Count of all possible values of X such that A % X = B are: "<<0;
    }
    else if(A == B){
        cout<<"Count of all possible values of X such that A % X = B are: "<<-1;
    }
    else{
        cout<<"Count of all possible values of X such that A % X = B are: "<<possible_values(A, B);
    }
    return 0;
}

出力

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

Count of all possible values of X such that A % X = B are: 1

計算量

• 時間計算量：O(√(A − B)) — 約数の探索を√(A − B) までの範囲で行うためです。
• 空間計算量：O(1) — 追加のデータ構造は使用しません。