\(2\) 直線の組は \(\frac{M(M-1)}{2}\) 通りあります。交わる直線の組の個数を求める問題ですが、余事象を考えて交わらない直線の組を数えることを考えます。実際に答えを求めるときは \(\frac{M(M-1)}{2}\) から交わらない直線の組の個数を引けば良いです。

\(2\) つの直線が交わらないとはその \(2\) つの直線が平行であることと同値です。では平行な直線の組を数え上げることではできるでしょうか。

直線 \(l_1\) と直線 \(l_2\) が平行、直線 \(l_2\) と直線 \(l_3\) げ平行であるとき直線 \(l_1\) と直線 \(l_3\) も平行です。これは傾きが同じ直線は全て互いに平行であるという特徴からもわかります。逆に、傾きが異なる \(2\) 直線は必ず交わります。つまり、ある傾きの直線が \(k\) 本あるなら \(\frac{k(k-1)}{2}\) 個の平行な直線の組があります。

以上より、\(M\) 本の直線をその傾きで分類することができれば答え求られます。実際に分類する方法について考えます。

実は、\((A_i+B_i) \bmod N\) で分類することができます。点 \(A_i\) と点 \(B_i\) を通る直線を取って、点 \(A_i\) から時計回りに \(k\) 個目の点、点 \(B_i\) から反時計回りに \(k\) 個目の点を通る直線が点 \(A_i\) と点 \(B_i\) を通る直線と平行であると考えるとわかりやすいです。

実装の際は答えが 32bit整数型ではオーバーフローすることがあることに気をつける必要があります。

実装例(C++):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> cnt(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        cnt[(a + b) % n]++;
    }
    ll ans = (ll)m * (m - 1) / 2;
    for (auto e : cnt) {
        ans -= e * (e - 1) / 2;
    }
    cout << ans << endl;
}