计算 GCD 等于 C++ 中给定数的自然数对

Z时代
2024-01-10
分类：综合

我们给出了三个输入变量，分别是“start”、“end”和“number”。目标是在开始和结束之间找到 GCD 值等于“数字”的数字对。例如GCD(A,B)=number 并且 A、B 都在 [start,end] 范围内。

让我们通过例子来理解。

输入- 开始=5 结束=20 数字=8

输出- GCD 等于给定数的自然数对的计数为 - 3

解释- 5 到 20 之间的对使得 GCD 为 8 是 - (8,8), (8,16), (16,8)

输入- 开始=5 结束=20 数字=7

输出- GCD 等于给定数的自然数对的计数为 - 2

解释- 20 到 30 之间的对使得 GCD 为 7 是 - (21,28), (28,21)

下面程序中使用的方法如下

我们将使用两种方法。第一个简单的方法，我们将使用从 i=start 到 i<=end 的 for 循环和从 j=start 到 j<=end 的内部循环遍历。对于每个pair(i,j)检查 if GCD(i,j)==number。如果为真增量计数。

将变量 start、end 和 number 作为整数。
函数GCD(int a, int b)是递归的，并返回传递给它的参数 a,b 的 GCD。
如果 b 非零，它会以 GCD(b,a%b) 的形式递归调用自己，否则返回 a。
函数GCD_pairs(int start, int end, int number)采用边界变量 start、end 和变量 number，并返回 start 和 end 之间具有 gcd=number 的对。
取初始计数为 0。
对每个成员使用两个 for 循环。从 i=start 到 i<=end 的外循环和从 j=start 到 j<=end 的内循环。
检查是否为对 (i,j), GCD(i,j)==number。如果为真，则增加计数。
最后我们将得到 gcd=number 的对的总数。
返回计数作为结果。

有效的方法

在这种方法中，我们将更新 start 和 end 的值。对于pair(i,j)gcd=number，i,j 都应该被 'number 整除。至多 (end-start)/numberno.s将完全除以“number”。为了得到可以被'number'整除的start和end之间的数字，我们将从start = (start + number - 1) / number到end = end / number遍历；因此，对于每个这样的数字，如果gcd(i,j)==1，则为这样的对(i,j)增加计数。

将变量 start、end 和 number 作为整数。
更新开始 = (start+number - 1)/number。并且结束=结束/数字。
函数GCD(int a, int b)是递归的，并返回传递给它的参数 a,b 的 GCD。
如果 b 非零，它会以 GCD(b,a%b) 的形式递归调用自己，否则返回 a。
函数GCD_pairs(int start, int end, int number)采用边界变量 start、end 和变量 number，并返回 start 和 end 之间具有 gcd=number 的对。
取初始计数为 0。
对每个成员使用两个 for 循环。从 i=start 到 i<=end 的外循环和从 j=start 到 j<=end 的内循环。
检查是否对 (i,j), GCD(i,j)==1。如果为真，则增加计数。
最后我们将得到 gcd=number 的对的总数。
返回计数作为结果。

示例（幼稚的方法）

#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
   return b ? GCD(b, a % b) : a; }
int GCD_pairs(int start, int end, int number){
   int count = 0;
   for (int i = start; i <= end; i++){
      for (int j = start; j <= end; j++){
         if (GCD(i, j) == number){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int start = 10, end = 30, number = 10;
   cout<<"GCD等于给定数的自然数对的计数是： "<<GCD_pairs(start, end, number) << endl;
   return 0;
}

输出结果

如果我们运行上面的代码，它将生成以下输出 -

GCD等于给定数的自然数对的计数是： 7

示例（有效方法）

#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
   return b ? GCD(b, a % b) : a;
}
int GCD_pairs(int start, int end, int number){
   int count = 0;
   for (int i = start; i <= end; i++){
      for (int j = start; j <= end; j++){
         if (GCD(i, j) == 1){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int start = 10, end = 30, number = 10;
   start = (start + number - 1) / number;
   end = end / number;
   cout<<"GCD等于给定数的自然数对的计数是： "<<GCD_pairs(start, end, number) << endl;
return 0;
}