Chúng ta được cung cấp đầu vào N. Mục đích là tìm tất cả các cặp A, B sao cho 1 <=A <=N và 1 <=B <=N và GCD (A, B) là B. Tất cả các cặp đều có giá trị lớn nhất ước số chung là B.
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - N =5
Đầu ra - Đếm số cặp (A <=N, B <=N) sao cho gcd (A, B) là B là - 10
Giải thích
Các cặppairs (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.
Đầu vào - N =50
Đầu ra - Đếm số cặp (A <=N, B <=N) sao cho gcd (A, B) là B là - 207
Giải thích
Các cặppairs (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)
Tương tự các cặp số khác như (4,2), (6,3), (8,2), (8,4), ........... (50,25). Tổng số 207
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Có thể có nhiều cách tiếp cận để giải quyết vấn đề đã cho, tức là cách tiếp cận ngây thơ và cách tiếp cận hiệu quả. Vì vậy, trước tiên chúng ta hãy xem xét cách tiếp cận ngây thơ .
-
Lấy một số nguyên N làm đầu vào.
-
Hàm GCD (int A, int B) nhận hai số nguyên và trả về ước số chung lớn nhất của A và B. Hàm này tính toán đệ quy gcd.
-
Nếu bất kỳ A hoặc B nào là 0 thì trả về một giá trị khác. Nếu cả hai đều bằng nhau, trả về bất kỳ giá trị nào trong hai giá trị. Nếu A> B trả về (A-B, B). Nếu B lớn hơn, trả về gcd (B-A, A). Cuối cùng, chúng tôi nhận được giá trị gcd.
-
Hàm count_pairs (int N) nhận N và trả về số cặp sao cho trong cặp (A, B), B là gcd và cả hai đều nằm trong phạm vi [1, N].
-
Lấy giá trị ban đầu là count =0 cho số cặp như vậy.
-
Đối với mỗi giá trị của cặp, chạy vòng lặp for i =1 đến i =N đối với A và lồng vào vòng lặp j =1 t j =N đối với B.
-
Tạo một cặp (i, j) và chuyển tới GCD (i, j). Nếu kết quả bằng j. Số lượng tăng dần.
-
Kết quả là ở cuối cả hai vòng lặp.
Cách tiếp cận hiệu quả
Như chúng ta có thể thấy gcd (a, b) =b có nghĩa là a luôn là bội của b. Tất cả các bội của b (1 <=b <=N) nhỏ hơn N sẽ tạo thành một cặp. Đối với một số i nếu bội số của i nhỏ hơn tầng (N / i) sẽ được tính.
-
Hàm count_pairs (int N) nhận N và trả về số cặp sao cho trong cặp (A, B), B là gcd và cả hai đều nằm trong phạm vi [1, N].
-
Lấy giá trị ban đầu là count =0 cho số cặp như vậy.
-
Lấy biến tạm thời temp =N và i =1.
-
Sử dụng while (i <=N) thực hiện theo các bước sau
-
Đối với mỗi tôi tính toán giới hạn bội số là j =N / temp
-
Số cặp cho dòng điện i sẽ là temp * (i-j + 1). Thêm vào bộ đếm.
-
Đặt i =j + 1. Đối với B tiếp theo của (A, B).
-
Đặt temp =N / i cho lần lặp tiếp theo.
-
Ở cuối vòng lặp while, trả về kết quả là số lượng.
Ví dụ (cách tiếp cận ngây thơ)
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: 8
Ví dụ (Cách tiếp cận hiệu quả)
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: 8