HELP

Cho dãy a gồm n số nguyên dương. Hãy cho biết có bao nhiêu cặp số trong dãy có tổng chia hết cho 3. Nói cách khác, bạn phải đếm xem có bao nhiêu cặp chỉ số i, j (1 ≤ i < j ≤ n) sao cho tổng a_i + a_j chia hết cho 3.

Dữ liệu:

• Dòng 1: Một số nguyên duy nhất n (1 ≤ n ≤ 10⁵).
• Dòng 2: Ghi n số nguyên dương a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁵, ) là các phần tử của dãy.

Kết quả:

• Một dòng duy nhất ghi số lượng cặp số của dãy a có tổng chia hết cho 3.

Ví dụ:

BAI4.INP

BAI4.OUT

Giải thích

5

3 4 2 3  4

3

3 cặp số tìm được có chỉ số là: (1,4) (2,3) (3,5)

4

3 6 9 12

6

6 cặp số tìm được có chỉ số là: (1,2) (1,3), (1,4), (2,3) (2,4) (3,4)

Hint:

lấy từng phần tử của A chia cho 3 tìm phần tử sử dụng mảng đánh dấu

a[n % 3]++

tính giá tri: (a[0] * (a[0] - 1)) / 2 + (a[1] * a[2])

(a[0] * (a[0] - 1)) / 2 chọn 2 phần tử chia hết cho 3

(a[1] * a[2]) : số cách chọn tổng 2 phần tử chia hết cho 3 

#include <bits/stdc++.h>
using namespace std;

void solve()
{
  long long tt, a[4] = {0, 0, 0, 0};
  cin >> tt;
  while (tt--){
    long long n;
    cin >> n;
    a[n % 3]++;
  }
  cout << a[0] * (a[0] - 1) / 2 + (a[1] * a[2]);
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  int tt = 1;
  // cin >> tt;
  while (tt--) solve();
  return 0;
}

#danglam228

#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
        ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    freopen("BAI4.INP", "r", stdin);
    freopen("BAI4.OUT", "w", stdout);
    cin >> n;
    vector<int> f(3, 0); 
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        f[x % 3]++;
    }
    long long e = (long long)f[0] * (f[0] - 1) / 2;
    e += (long long)f[1] * f[2];
    cout << e << endl;
    return 0;
}