概要

公式解説の \( (A_i + B_i) \mod N\) を使わず解いてみましょう。

\(A, B\) をそれぞれ \(-1\) して 0-indexed で考えると、\((A, B)=(1, N-1)\) のようなケースを除いて、直線上の \(1\) 点は \(0\) 、もう \(1\) 点は \(0\) 以外のどこかを通るように平行移動できます。

大きさ \(N\) 、各要素を \(0\) で初期化した配列を用意し、\((1,N-1)\) に平行な直線は添字 \(0\) で管理し、そうでないものは平行移動後、 \(0\) でない方を添字に持てば良いと考えられます。

平行移動の方法

点 \(0\) ( \(=\) 点 \(N\) ) からの距離を考え、点 \(A, B\) のうち、点 \(0\) に近い方を \(0\) に合わせにいくイメージです。

• \(A=N-B\) の場合

点 \(0\) から \(A, B\) への距離は等しいです。

点 \(0\) を通るように平行移動すると、直線は頂点 \(0\) のみ通ります。このケースは特別に、前述の通り添字 \(0\) で管理します。

• \(A<N-B\) の場合

点 \(0\) から \(A\) の距離が、\(0\) から \(B\) の距離より短いです。

\(A\) を \(0\) に合わせに行くイメージです。図を考えると、\(A\) 側を \(A\) 引くと、\(B\) 側は \(A\) 足すことで平行移動できます。よって、 \(A+B\) が添字になります。

• \(A>N-B\) の場合

点 \(0\) から \(A\) の距離が、\(0\) から \(B\) の距離より長いです。

\(B\) を \(N\) (点 \(0\) ) に合わせに行くイメージです。\(B\) に \(N-B\) 足すことになり、\(A\) は \(N-B\) 引くことで平行移動できます。よって、 \(A - N + B\) が添字になります。

余談

以上や、下記の実装例をぐっと睨むことでも \( (A_i + B_i) \mod N\) を思いつけます。

実装例

(C++, 132ms) https://atcoder.jp/contests/abc402/submissions/65055441

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll n, m; cin >> n >> m;
    ll ans = (m * (m - 1) / 2);
    vector<ll> cnt(n, 0);
    for(int i = 0; i < m; i ++) {
        ll a, b; cin >> a >> b;
        a --; b --;
        if (a == (n - b)) {
            ans -= cnt[0];
            cnt[0] ++;
        } else if (a < (n - b)) {
            ans -= cnt[a + b];
            cnt[a + b] ++;
        } else {
            ans -= cnt[a - n + b];
            cnt[a - n + b] ++;
        }
    }
    cout << ans << endl;
    return 0;
}