`=>` C++ Hai số nguyên dương A và B được gọi là bạn của nhau nếu chúng có chung ít nhất một chữ số. Cho một mảng A gồm N số nguyên dương. Hãy tìm số lượng cặp (i, j) thỏa mãn A[i] và A[j] là bạn của nhau với i <

Để giải bài toán này, chúng ta cần xác định số cặp số (A[i], A[j]) từ mảng A sao cho chúng có ít nhất một chữ số giống nhau. Theo yêu cầu của bài toán, nếu A[i] và A[j] có ít nhất một chữ số giống nhau thì chúng được gọi là "bạn của nhau".

### Giải thích chi tiết

1. Biểu diễn chữ số:
Mỗi số nguyên dương có thể được biểu diễn bằng một tập hợp các chữ số của nó. Chúng ta có thể sử dụng một biến bitmask (biến số bit) để đại diện cho các chữ số từ 0 đến 9. Ví dụ, nếu một số có chữ số '1' và '2', chúng ta có thể sử dụng bitmask như sau:
- Chữ số '0' tương ứng với bit 0 (2^0)
- Chữ số '1' tương ứng với bit 1 (2^1)
- Chữ số '2' tương ứng với bit 2 (2^2)
- ...
- Chữ số '9' tương ứng với bit 9 (2^9)

Nếu số có chữ số '1' và '2', bitmask sẽ là `0000000011` (tương đương với số thập phân là 3).

2. Tạo bitmask cho mỗi số:
Chúng ta cần duyệt qua mỗi số trong mảng và tạo bitmask tương ứng cho từng số.

3. Tính toán số lượng cặp:
Sau khi chúng ta đã lưu trữ bitmask của tất cả các số, chúng ta sẽ cần một cách để đếm số cặp có chữ số chung.
- Sử dụng một hashmap (hoặc mảng) để lưu số lần xuất hiện của mỗi bitmask.
- Chúng ta có thể duyệt qua từng bitmask và tính số lượng cặp mà nó có thể tạo ra với các bitmask khác nhau nếu chúng có ít nhất một bit chung. Điều này có thể được thực hiện bằng cách kiểm tra:
- Hai bitmask A và B có chung chữ số nếu A & B != 0.

4. Đếm số cặp:
Giả sử có `count[mask1]` là số lần xuất hiện của bitmask `mask1`, số cặp có thể tạo ra từ các số với bitmask `mask1` là:
- Nếu có `count[mask1]` số, thì số cặp là C(count[mask1], 2) = count[mask1] * (count[mask1] - 1) / 2.

Sau đó, chúng ta cộng tất cả các cặp cho các bitmask có chữ số chung.

### Mã nguồn C++

Dưới đây là mã C++ thực hiện giải thuật trên:

```cpp
#include
#include
#include
using namespace std;

long long countFriendPairs(const vector& A) {
unordered_map maskCount;
long long totalPairs = 0;

// Tạo bitmask cho mỗi số
for (long long number : A) {
int mask = 0;
while (number > 0) {
int digit = number % 10;
mask |= (1 << digit); // Thiết lập bit tương ứng với chữ số
number /= 10;
}
maskCount[mask]++;
}

// Tính số cặp cho các bitmask
for (const auto& [mask, count] : maskCount) {
totalPairs += (long long)count * (count - 1) / 2; // C(count, 2)
for (const auto& [otherMask, otherCount] : maskCount) {
if (mask < otherMask && (mask & otherMask)) { // đảm bảo mask1 < mask2 và có chữ số chung
totalPairs += (long long)count * otherCount;
}
}
}

return totalPairs;
}

int main() {
int T;
cin >> T; // số lượng test case
while (T--) {
int N;
cin >> N;
vector A(N);
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
cout << countFriendPairs(A) << endl;
}
return 0;
}
```

### Kết luận
Mã nguồn trên sẽ đọc dữ liệu từ đầu vào, hình thành các bitmask cho mỗi số trong mảng, và kiểm tra tất cả các cặp bitmask để tính số lượng cặp số là "bạn của nhau". Phương pháp này có thời gian xử lý hiệu quả do tính chất sử dụng phép toán bitwise để kiểm tra sự trùng lặp chữ số.