Question link:https://www.luogu.org/problem/T84891
topic
T1Ideas
If part A conflicts with part B, and part A conflicts with part C, then part B and part C also conflict.
That is to say, among part A, part B, and part C, we can only select one part.
Part A, Part B, and Part C have a common feature, that is, the same value after %K.
So just put all the input content into a set after %K, and finally output the size of the set.
代码
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <set>
using namespace std;
const int MAXN = 1e5 + 100;
int arr[MAXN];
bitset<MAXN> vis;
int main() {
vis.reset();
int n, k;
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++)
scanf("%d", &arr[i]);
//按照惯例,暴力做法注释
// sort(arr, arr + n);
// for(int i = 0; i < n; i++) {
// for(int j = i + 1; j < n; j++) {
// if(!vis[j]) {
// if((arr[j] - arr[i]) % k == 0)
// vis[j] = true;
// }
// }
// }
set<int> s;
for(int i = 0; i < n; i++)
s.insert(arr[i] % k);
// printf("%d\n", n - vis.count());
printf("%d\n", s.size());
return 0;
}