计算成对的数目(A <= N,B <= N)以使gcd(A,B)在C ++中为B
我们得到一个输入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(intA,intB)取两个整数,并返回A和B的最大公约数。它递归计算gcd。
如果A或B中的任何一个为0,则返回另一个。如果两者相等,则返回两个值中的任何一个。如果A>B返回(AB,B)。如果B更大,则返回gcd(BA,A)。最后,我们得到gcd值。
函数count_pairs(intN)取N,并返回对数,以使对(A,B)中的B为gcd,且两者均在range[1,N]内。
对于这样的对的数量,取初始值为count=0。
对于每对值,对A的循环i=1到i=N运行,对B的循环j=1tj=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(intN)取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