資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
