Chia hết cho 3
Xem dạng PDF
Gửi bài giải
Đ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
Người đăng:
Dạng bài
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 ai + aj chia hết cho 3.
Dữ liệu:
Dòng 1: Một số nguyên duy nhất n (1 ≤ n ≤ 105). Dòng 2: Ghi n số nguyên dương a1, a2, ..., an (1 ≤ ai ≤ 105, mọi i=1..n) 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. Ghi chú:
Subtask 1 (50% số test) n ≤ 100 Subtask 2 (50% số test) không có ràng buộc gì thêm. Ví dụ:
Inp:
5
3 4 2 3 4
Out:
3
Ví dụ 3 cặp số tìm được có chỉ số là: (1,4) (2,3) (3,5)
Bình luận
Code tham khảo:
include <bits/stdc++.h>
using namespace std; long long a[1000006]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; a[i] %= 3; } unordered_map<int, int> cnt; for (int i = 0; i < n; i++) cnt[a[i]]++; long long dem = 0; for (int i = 0; i < n; i++) { cnt[a[i]]--; int k = (3 - a[i]) % 3; dem += cnt[k]; } cout << dem; return 0; }