Đếm dãy con có GCD bằng 1 trong C++

Cho mảng số nguyên. Đếm số dãy con (subsequence) có GCD (ước chung lớn nhất) bằng 1.

Ví dụ: {3, 4, 8, 16} → 7 (các dãy: (3,4), (3,8), (3,16), (4,3), (8,3), (16,3), (3,4,8)).

Lưu ý: Code mẫu dùng vòng lặp lồng nhau kiểm tra cặp (i,j), nhưng giải thích đề cập đến "sub-sequences". Cách tiếp cận đúng cho dãy con là dùng DP trên GCD, tuy nhiên bài này trình bày cách đơn giản đếm cặp có GCD=1.

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

Count of number of sub-sequences with GCD 1 are: 7