数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中计算最大公约数为给定数字的自然数对
我们给出三个输入变量“start”、“end”和“number”。目标是在start和end之间找到最大公约数（GCD）值为“number”的数字对。例如，GCD(A,B)=number，并且A、B都在[start,end]范围内。
让我们通过例子来理解。
输入 − start=5 end=20 number=8
输出 − 最大公约数为给定数字的自然数对的数量为 − 3
解释 − 5到20之间，最大公约数为8的数对为 − (8,8), (8,16), (16,8)
输入 − start=5 end=20 number=7
输出 − 最大公约数为给定数字的自然数对的数量为 − 2
解释− 20到30之间，最大公约数为7的数对为 − (21,28), (28,21)
下面程序中使用的方法如下
我们将使用两种方法。第一种是朴素的方法，我们将使用for循环从i=start遍历到i<=end，内循环从j=start遍历到j<=end。对于每一对(i,j)，检查GCD(i,j)==number是否成立。如果成立，则计数器加1。
将变量start、end和number作为整数。
函数GCD(int a, int b)是递归函数，返回传递给它的参数a、b的最大公约数。
如果b不为零，则递归调用自身为GCD(b,a%b)，否则返回a。
函数GCD_pairs(int start, int end, int number)接受边界变量start、end和变量number，并返回start和end之间最大公约数为number的数对。
将初始计数设置为0。
使用两个for循环来遍历每一对的每个成员。外循环从i=start遍历到i<=end，内循环从j=start遍历到j<=end。
检查对于数对(i,j)，GCD(i,j)==number是否成立。如果成立，则计数器加1。
最后，我们将得到最大公约数为number的数对的总数。
返回计数作为结果。
高效方法
在这种方法中，我们将更新start和end的值。对于数对(i,j)来说，要使最大公约数为number，i和j都应该能被‘number’整除。最多会有(end-start)/number个数字能被‘number’整除。为了得到start和end之间能被‘number’整除的数字，我们将从start = (start + number - 1) / number遍历到end = end / number；因此，对于每个这样的数字，如果gcd(i,j)==1，则为这样的数对(i,j)增加计数。
将变量start、end和number作为整数。
更新start = (start+number - 1)/number。以及end=end/number。
函数GCD(int a, int b)是递归函数，返回传递给它的参数a、b的最大公约数。
如果b不为零，则递归调用自身为GCD(b,a%b)，否则返回a。
函数GCD_pairs(int start, int end, int number)接受边界变量start、end和变量number，并返回start和end之间最大公约数为number的数对。
将初始计数设置为0。
使用两个for循环来遍历每一对的每个成员。外循环从i=start遍历到i<=end，内循环从j=start遍历到j<=end。
检查对于数对(i,j)，GCD(i,j)==1是否成立。如果成立，则计数器加1。
最后，我们将得到最大公约数为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<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
return 0;
}输出
如果我们运行上面的代码，它将生成以下输出：
Count of pairs of natural numbers with GCD equal to given number are: 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<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
return 0;
}输出
如果我们运行上面的代码，它将生成以下输出：
Count of pairs of natural numbers with GCD equal to given number are: 7
978 次浏览
