数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用 C++ 统计满足 gcd(A, B) = B 的数对 (A <= N, B <= N) 的数量
给定一个输入 N。目标是找到所有满足 1<=A<=N 和 1<=B<=N 且 GCD(A, B) 为 B 的数对 (A, 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，则返回 (A-B,B)。如果 B 大于 A，则返回 gcd(B-A,A)。最后我们得到 gcd 值。
函数 count_pairs(int N) 接收 N 并返回满足条件的数对的数量，其中在数对 (A,B) 中，B 是 gcd 且两者都在范围 [1,N] 内。
将初始值设置为 count =0，表示此类数对的数量。
对于每个数对的值，运行循环 i=1 到 i=N 对应 A，以及嵌套循环 j=1 到 j=N 对应 B。
创建一个数对 (i,j) 并将其传递给 GCD(i,j)。如果结果等于 j，则递增 count。
在两个循环结束时，返回 count 作为结果。
高效方案
我们可以看到 gcd(a,b)=b 表示 a 始终是 b 的倍数。所有小于 N 的 b (1<=b<=N) 的倍数都会构成一个数对。对于一个数字 i，如果 i 的倍数小于 floor(N/i)，则会被计数。
函数 count_pairs(int N) 接收 N 并返回满足条件的数对的数量，其中在数对 (A,B) 中，B 是 gcd 且两者都在范围 [1,N] 内。
将初始值设置为 count =0，表示此类数对的数量。
使用临时变量 temp=N 和 i=1。
使用 while (i<=N) 执行以下操作
对于每个 i，计算倍数的限制为 j=N/temp
当前 i 的数对数量为 temp*(i-j+1)。将其加到 count 中。
设置 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
558 次浏览
