Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Java
4.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
28Tech là người rất thích số 28, anh ta cho bạn mảng A[] gồm N phần tử, bạn hãy đếm xem trong mảng có bao nhiêu cặp số A[i], A[j] với i khác j mà khi cộng với nhau sẽ tạo thành 1 số chia hết cho 28.
Đầu vào
Dòng 1 là N : số phần tử trong mảng
Dòng 2 là N phần tử cách nhau 1 khoảng trắng
Giới hạn
1<=N<=10^6
0<=A[i]<=10^9
Đầu ra
In ra số cặp thỏa mãn
Ví dụ :
Input 01
5
1 14 14 27 27
Output 01
3
Bình luận
code cho ae tham khao
include <bits/stdc++.h>
using namespace std; long long n,a[1000005],d1,d2,kq,d28; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; if(a[i]%28==0) {a[i]=0;d28++;} else a[i]=a[i]%28; } sort(a+1,a+n+1); for(long long i=1;i<=n;i++) { d1=lowerbound(a+i+1,a+n+1,28-a[i])-a; d2=upperbound(a+i+1,a+n+1,28-a[i])-a-1; if(d1<=d2) kq+=d2-d1+1; } kq+=d28*(d28-1)/2; cout<<kq; return 0; }
time erorr
hello world
vận dụng: A % 28 = 0 <=> (a%28 + b%28) % 28 = 0 => đặt x = a%28, y=b%28 <=> (x+y)%28 = 0 mà x, y <= 28 -> x+y=28 -> bài toán trở thành tìm, đếm cặp số dư bằng 28. (TH đặc biệt: x=y=14 , x=y=0 -> xét riêng)
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.