在 C++ 中计算满足 A % X = B 的所有 X 的可能值个数

给定两个整数 A 和 B 以及一个数字 X。目标是找到 X 的可能值个数，使得 A%X=B。如果 A==B，则 X 有无限多个可能值，因此返回 -1。如果 A < B，则没有解，因此返回 0。如果 A>B，则返回 (A-B) 的约数个数作为结果。

例如

输入

A=5, B=2

输出

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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

解释

5%3=2. So X is 3 here.

输入

A=10, B=10

输出

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

解释

Here A==B so there are infinite solutions so −1 is returned.

以下程序中使用的算法如下 −

在这种方法中，我们将使用 for 循环从 i=1 到 i*i<=(A−B) 计算 (A-B) 的约数。如果任何 i 完全整除 (A-B)，则相应地更新计数。

  • 输入整数 A 和 B。

  • 如果 A<B，则打印 0 作为结果。

  • 如果 A==B，则打印 -1 作为结果。

  • 对于 A>B，函数 possible_values(int A, int B) 获取 A 和 B 并返回满足 A % X = B 的所有 X 的可能值个数。

  • 将初始计数设置为 0，X=A−B。

  • 使用 for 循环从 i=1 到 i*i<(A−B) 遍历，以计算 X 的约数。

  • 如果任何 i 完全整除 X，则令 temp=i，temp_2=B−1，如果 i*i!=X，则设置 temp_2 = X / i。

  • 如果 temp>B 且 temp_2 >B，则递增计数。

  • 在循环结束时，返回计数作为结果。

示例

 在线演示

#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

更新于：2021年1月5日

174 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告