Đề bài:
Thuật toán:
- Gọi \(cnt[i]\) là số các số chia mod k = i trong tập \(S\).
- Theo đề bài ta có: \(KQ = KQ + max(cnt[i], cnt[k-i])\) với \(i=1..k/2\).
- Chú ý nếu n mod 2 = 0 thì ta không cộng \(cnt[n/2]\) vào KQ mà chỉ cộng 1 thôi.
Code:
- C++ (xem)
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; const ll mod=1000000007; ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} int n, k, i, j, a[200004], cnt[500], ans; int main() { cin >> n >> k; for (int i=1; i<=n; i++) cin >> a[i]; for (int i=1; i<=n; i++) { a[i] = a[i] % k; ++cnt[a[i]]; } for (int i=1; i<=k/2; i++) { ans = ans + max(cnt[i], cnt[k-i]); } if (k%2 == 0) { ans -= cnt[k/2]; if (cnt[k/2]>0) ans++; } if (cnt[0] > 0) ans++; cout << ans; return 0; } |
Speak Your Mind