Chúng tôi đã đưa ra ba biến đầu vào là "start", "end" và "number". Mục đích là tìm các cặp số từ đầu đến cuối có giá trị GCD bằng ‘number’. Ví dụ:GCD (A, B) =number và cả A, B đều nằm trong phạm vi [bắt đầu, kết thúc].
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - start =5 end =20 number =8
Đầu ra - Đếm các cặp số tự nhiên có GCD bằng số đã cho là - 3
Giải thích - Các cặp từ 5 đến 20 sao cho GCD là 8 là - (8,8), (8,16), (16,8)
Đầu vào - start =5 end =20 number =7
Đầu ra - Đếm các cặp số tự nhiên có GCD bằng số đã cho là - 2
Giải thích - Các cặp từ 20 đến 30 sao cho GCD là 7 là - (21,28), (28,21)
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Chúng tôi sẽ sử dụng hai cách tiếp cận. Cách tiếp cận ngây thơ đầu tiên, trong đó chúng ta sẽ duyệt qua bằng cách sử dụng vòng lặp for từ i =start đến i <=end và vòng lặp bên trong từ j =start đến j <=end. Đối với mỗi cặp (i, j), hãy kiểm tra xem số GCD (i, j) ==. Nếu số gia tăng đúng.
-
Lấy các biến bắt đầu, kết thúc và số dưới dạng số nguyên.
-
Hàm GCD (int a, int b) là đệ quy và trả về GCD của các đối số a, b được truyền cho nó.
-
Nếu b khác 0, nó sẽ gọi chính nó một cách đệ quy là GCD (b, a% b) nếu không nó trả về a.
-
Hàm GCD_pairs (int start, int end, int number) nhận các biến biên bắt đầu, kết thúc và số biến và trả về các cặp giữa đầu và cuối có gcd =number.
-
Lấy số lượng ban đầu là 0.
-
Sử dụng hai vòng lặp for cho mỗi thành viên của cặp. Vòng lặp bên ngoài từ i =start đến i <=end và vòng lặp bên trong từ j =start đến j <=end.
-
Kiểm tra xem cặp (i, j), GCD (i, j) ==số. Nếu đúng, hãy đếm gia số.
-
Cuối cùng, chúng tôi sẽ nhận được tổng số các cặp với gcd =number.
-
Kết quả là số lượt trả lại.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, chúng tôi sẽ cập nhật các giá trị của bắt đầu và kết thúc. Để cặp (i, j) có gcd =number thì cả i, j đều chia hết cho ‘number. Sẽ có nhiều nhất (end-start) / number no.s sẽ chia hết ‘số’. Để nhận được các số từ đầu đến cuối chia hết cho ‘number’, chúng ta sẽ duyệt từ start =(start + number - 1) / number đến end =end / number; Vì vậy, đối với mỗi số như vậy nếu gcd (i, j) ==1 thì số gia tăng cho cặp như vậy (i, j).
-
Lấy các biến bắt đầu, kết thúc và số dưới dạng số nguyên.
-
Cập nhật start =(start + number - 1) / number. Và end =end / number.
-
Hàm GCD (int a, int b) là đệ quy và trả về GCD của các đối số a, b được truyền cho nó.
-
Nếu b khác 0, nó sẽ gọi chính nó một cách đệ quy là GCD (b, a% b) nếu không nó trả về a.
-
Hàm GCD_pairs (int start, int end, int number) nhận các biến biên bắt đầu, kết thúc và số biến và trả về các cặp giữa đầu và cuối có gcd =number.
-
Lấy số lượng ban đầu là 0.
-
Sử dụng hai vòng lặp for cho mỗi thành viên của cặp. Vòng lặp bên ngoài từ i =start đến i <=end và vòng lặp bên trong từ j =start đến j <=end.
-
Kiểm tra xem cặp (i, j), GCD (i, j) ==1. Nếu đúng, hãy đếm gia số.
-
Cuối cùng, chúng tôi sẽ nhận được tổng số các cặp với gcd =number.
-
Kết quả là số lượt trả lại.
Ví dụ (cách tiếp cận ngây thơ)
#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
return b ? GCD(b, a % b) : a; }
int GCD_pairs(int start, int end, int number){
int count = 0;
for (int i = start; i <= end; i++){
for (int j = start; j <= end; j++){
if (GCD(i, j) == number){
count++;
}
}
}
return count;
}
int main(){
int start = 10, end = 30, number = 10;
cout<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
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 of pairs of natural numbers with GCD equal to given number are: 7
Ví dụ (Cách tiếp cận hiệu quả)
#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
return b ? GCD(b, a % b) : a;
}
int GCD_pairs(int start, int end, int number){
int count = 0;
for (int i = start; i <= end; i++){
for (int j = start; j <= end; j++){
if (GCD(i, j) == 1){
count++;
}
}
}
return count;
}
int main(){
int start = 10, end = 30, number = 10;
start = (start + number - 1) / number;
end = end / number;
cout<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
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 of pairs of natural numbers with GCD equal to given number are: 7