[HSG-QH_DL_NA_24] Chia hết

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Pascal, Python

Cho dãy ~a~ gồm ~n~ số nguyên dương.

Yêu cầu

Hãy cho đếm xem có bao nhiêu cặp chỉ số ~i,\ j~ ~(1 \le i < j \le n)~ sao cho tổng ~a_{i} + a_{j}~ chia hết cho ~3~.

Dữ liệu đầu vào

Gồm hai dòng:

Dòng 1: Một số nguyên duy nhất ~n~ ~(1 \le n \le 10^5)~.
Dòng 2: Ghi ~n~ số nguyên dương ~a_{1}, a_{2}, ..., a_n~ ~(1 \le a_{i} \le 10^5,\ \forall i = 1 \rightarrow n)~ là phần tử của dãy.

Dữ liệu đầu ra

Gồm một dòng duy nhất ghi số lượng cặp số của dãy ~a~ có tổng ~a_{i} + a_{j}~ chia hết cho ~3~.

Ràng buộc dữ liệu

50% số test có ~n \le 100~.
50% số test còn lại không ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5
3 4 2 3 4

OUTPUT

Ví dụ 2

INPUT

4
3 6 9 12

OUTPUT

Bình luận

Hãy đọc nội quy trước khi bình luận.

nguyendanhduong_vp_526 đã bình luận lúc 3, Tháng 12, 2024, 3:04

include <bits/stdc++.h>

define ll long long

using namespace std;

int main() { ll n; cin >> n; ll a[n], count[3] = {0}; // count[0] là số phần tử dư 0, count[1] dư 1, count[2] dư 2

// Đọc mảng và đếm số phần tử có phần dư 0, 1, 2 khi chia cho 3
for (ll i = 0; i < n; i++) {
    cin >> a[i];
    count[a[i] % 3]++; // Đếm phần tử theo phần dư khi chia cho 3
}

// Tính số cặp thỏa mãn điều kiện (a[i] + a[j]) % 3 == 0
ll result = count[0] * (count[0] - 1) / 2; // Cặp (i, j) với a[i] % 3 == 0 và a[j] % 3 == 0
result += count[1] * count[2]; // Cặp (i, j) với a[i] % 3 == 1 và a[j] % 3 == 2

cout << result;

return 0;

}

5

nguyenminhquang_vp_906 đã bình luận lúc 3, Tháng 12, 2024, 2:56

hi ae