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

2023-06-21 14:17:03 184

我们给出了三个输入变量，分别是“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)检查ifGCD(i,j)==number。如果为真增量计数。

将变量start、end和number作为整数。

函数GCD(inta,intb)是递归的，并返回传递给它的参数a,b的GCD。

如果b非零，它会以GCD(b,a%b)的形式递归调用自己，否则返回a。

函数GCD_pairs(intstart,intend,intnumber)采用边界变量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(inta,intb)是递归的，并返回传递给它的参数a,b的GCD。

如果b非零，它会以GCD(b,a%b)的形式递归调用自己，否则返回a。

函数GCD_pairs(intstart,intend,intnumber)采用边界变量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 
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等于给定数的自然数对的计数是： 7
示例（有效方法）
#include 
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等于给定数的自然数对的计数是： 7

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

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

有效的方法

示例（幼稚的方法）

示例（有效方法）

热门推荐

随机推荐