Đếm số chuỗi con có GCD 1 trong C ++

Chúng ta được cung cấp một mảng gồm các phần tử nguyên và nhiệm vụ là tìm các dãy con từ mảng đã cho có GCD là 1. GCD là ước chung lớn nhất của hai hoặc nhiều hơn số nguyên chia hoàn toàn và lớn nhất cho các số đã cho.

Đầu vào - int arr [] ={3, 4, 8, 16}

Đầu ra - Đếm số dãy con có GCD 1 là - 7

Giải thích -

Các dãy con có thể được hình thành từ mảng đã cho với GCD là 1 là (3, 4), (3, 8), (3, 16), (4, 3), (8, 3), (16, 3), (3, 4, 8)

Đầu vào - int arr [] ={5, 7, 10}

Đầu ra - Đếm số dãy con có GCD 1 là - 3

Giải thích -

Các dãy con có thể được hình thành từ mảng đã cho với GCD là 1 là (5, 7), (7, 10), (5, 7, 10)

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Nhập một mảng các phần tử số nguyên có kích thước bất kỳ.

• Tính toán kích thước của một mảng và chuyển dữ liệu vào hàm để xử lý thêm

• Khai báo số lượng biến tạm thời để lưu trữ số lượng các chuỗi con với GCD là 1

• Bắt đầu vòng lặp FOR từ i đến 0 cho đến hết kích thước của một mảng

• Bên trong vòng lặp, bắt đầu một vòng lặp FOR khác từ j đến 0 cho đến khi kích thước của một mảng

• Bên trong vòng lặp, kiểm tra IF GCD (arr [i], arr [j]) =TRUE sau đó tăng số lượng lên 1

• Số lần trả lại

• In kết quả.

Ví dụ

# include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
   if (a == 0)
      return b;
   return gcd(b % a, a);
}
int GCD_1(int arr[],int size){
   int count = 0;
   for(int i=0;i<size;i++){
      for(int j=0;j<=size;j++){
         if(gcd(arr[i],arr[j])==1){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {3, 4, 8, 16};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of number of sub-sequences with GCD 1 are: "<<GCD_1(arr, size);
   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 number of sub-sequences with GCD 1 are: 7