CodeFestival2016 Final D.Pair Cards

問題

N枚のカードがあり、カードiには整数X_iが書かれている。
今、「書かれた数字が同じ」または「和がMの倍数」になるような2枚のカードをペアにする。
最大で何ペア作れるか？

制約

2 <= N <= 10^5
1 <= M <= 10^5
1 <= X_i <= 10^5

解説

https://cf16-final.contest.atcoder.jp/data/other/cf16-final/editorial.pdf

「和がMの倍数」になるようなペアの処理は、X_i mod Mでグルーピングすると、余りがjのグループとM-jのグループのペアを取ればMの倍数になる。
(ただし、mod M == 0か、mod M == M/2(ただし、M mod 2==0)の場合は、同じグループ内でペアを取る)

こうすれば、グループAとグループBでの最大マッチングを求めて足し合わせればよくなる。

|A|==|B|の場合は、|A|個ペアが作れる。
|A|<|B|の場合、|A|個のペアは作れることがわかるが、|B|-|A|個のうち、「書かれた数字が同じ」場合はペアを取ることができる。
したがって、グループBの方で、|B|-|A|枚以下のカードを使って、書かれた数字が同じになるペアの最大ペア数をmとすると、「m+|A|」ペアが最大マッチングになる。