Ý tưởng chính bài này là đếm bằng hai cách. Với một đại lượng nào đó, ta sẽ tìm cách tính nó bằng hai cách khác nhau để tạo ra một phương trình.

Giả sử ta có một đồ thị \(n\) đỉnh, hai đỉnh \(i\) và \(j\) được nối với nhau bởi cạnh màu đỏ nếu \(gcd(a_i, a_j) = 1\) và màu xanh nếu \(gcd(a_i, a_j) > 1\). Bài toán quy về: Đếm có bao nhiêu tam giác có 3 cạnh đỏ hoặc 3 cạnh xanh.

Đầu tiên, nhận thấy chỉ có \(4\) loại tam giác: 3 cạnh đỏ, 3 cạnh xanh, 2 đỏ 1 xanh, 2 xanh 1 đỏ. Gọi số lượng mỗi loại là \(A, B, C, D\). Ta cần tìm \(A + B\).

**Phương trình 1: ** \(A + B + C + D = C_n^3\). Đây chính là tổng số tam giác

**Phương trình 2: ** $3A + C = $ Số góc đỏ.

Quy ước số góc đỏ là số góc \(\angle XYZ\) mà \(XY\) và \(YZ\) có màu đỏ. Ta có 2 cách tính đại lượng này.

*Cách 1: * Trong mỗi tam giác 3 đỏ \(XYZ\), ta có \(3\) góc đỏ. Mỗi tam giác 2 đỏ 1 xanh có \(1\) góc đỏ.

*Cách 2: * Ta có thể tính bằng cách đếm có bao nhiêu bộ \((i, j, k)\) mà \((i, j)\) màu đỏ và \((j, k)\) màu đỏ. Ta có thể tính bằng cách for \(j\) và với mỗi số \(j\), đếm xem có bao nhiêu đỉnh nối với nó bằng cạnh đỏ, gọi là \(x\). Số góc đỏ tại \(j\) sẽ là \(C_x^2\). Cuối cùng tổng hết cho tất cả \(j\).

Từ 2 cách trên, ta có được phương trình \(3A + C = ...\)

**Phương trình 3: ** \(3B + D\) = Số góc xanh (tính hoàn toàn tương tự)

Từ 3 phương trình trên, ta có thể tính được \(A + B\). Độ phức tạp là \(O(n^2)\).