我们给出了三个输入变量，分别是“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;
}输出结果如果我们运行上面的代码，它将生成以下输出 -
GCD等于给定数的自然数对的计数是： 7