我们得到一个输入N。目标是找到所有A，B对，使得1 <= A <= N和1 <= B <= N且GCD(A,B)为B。所有对都具有最大的常用除数B
让我们通过示例来理解。
输入-N = 5
输出-使得gcd(A,B)为B的对数（A <= N，B <= N）为-10
说明
pairs (A <= N, B <= N) such that gcd (A , B) is B are − (1,1), (2,1),(3,1),(4,1),(5,1),(2,2),(3,3),(4,2),(4,4), (5,5). Total 10.
输入-N = 50
输出-使得gcd(A,B)为B的对数（A <= N，B <= N）为-207
说明
pairs (A <= N, B <= N) such that gcd (A , B) is B are : (1,1), (2,1),(3,1),(4,1),(5,1).....(50,1) (2,2),(3,3),(4,4).....(50,50)
类似地，其他对如(4,2)，(6,3)，(8,2)，(8,4)，......(50,25)。总计207
解决给定问题的方法可以有多种，即幼稚方法和有效方法。因此，让我们首先来看一下幼稚的方法。
以整数N作为输入。
函数GCD（int A，int B）取两个整数，并返回A和B的最大公约数。它递归计算gcd。
如果A或B中的任何一个为0，则返回另一个。如果两者相等，则返回两个值中的任何一个。如果A> B返回(AB,B)。如果B更大，则返回gcd(BA,A)。最后，我们得到gcd值。
函数count_pairs（int N）取N，并返回对数，以使对(A,B)中的B为gcd，且两者均在range [1，N]内。
对于这样的对的数量，取初始值为count = 0。
对于每对值，对A的循环i = 1到i = N运行，对B的循环j = 1 tj = N嵌套。
配对(i,j)，然后传递给GCD(i,j)。如果结果等于j。增量计数。
在两个循环结束时，返回计数作为结果。
如我们所见，gcd(a,b)= b表示a始终是b的倍数。b（1 <= b <= N）的所有小于N的所有倍数将成对。对于数字i，如果i的倍数小于floor（N / i），将被计算在内。
函数count_pairs（int N）取N，并返回对数，以使对(A,B)中的B为gcd，且两者均在range [1，N]内。
对于这样的对的数量，取初始值为count = 0。
取临时变量temp = N和i = 1。
使用while（i <= N）进行以下操作
对于每个我计算的倍数极限为j = N / temp
当前i的对数将为temp *（i-j + 1）。加计数。
设置i = j + 1。对于(A,B)的下一个B.
为下一次迭代设置temp = N / i。
在while循环结束时，返回count作为结果。
#include <iostream>
using namespace std;
int GCD(int A, int B){
if (A == 0){
return B;
}
if (B == 0){
return A;
}
if (A == B){
return A;
}
if (A > B){
return GCD(A-B, B);
}
return GCD(A, B-A);
}
int count_pairs(int N){
int count = 0;
for(int i=1; i<=N; i++){
for(int j = 1; j<=N; j++){
if(GCD(i, j)==j){
count++;
}
}
}
return count;
}
int main(){
int N = 4;
cout<<"Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: "<<count_pairs(N);
return 0;
}输出结果
如果我们运行上面的代码，它将生成以下输出-
Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: 8
#include <bits/stdc++.h>
using namespace std;
int Count_pairs(int N){
int count = 0;
int temp = N;
int i = 1;
while(i <= N){
int j = N / temp;
count += temp * (j - i + 1);
i = j + 1;
temp = N / i;
}
return count;
}
int main(){
int N = 4;
cout<<"Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: "<<Count_pairs(N);
return 0;
}输出结果
如果我们运行上面的代码，它将生成以下输出-
Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: 8