Submission #65790650

---

Source Code Expand

// 綺麗に解きなおし

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

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n, m;
  cin >> n >> m;

  vector<int> a(m), b(m);
  for (int i=0; i<m; i++) {
    cin >> a.at(i) >> b.at(i);
  }

  //////////////// 出力変数定義 ////////////////

  // とりあえず、交わる交わらない関係なく、辺の組全パターン数を計算しておく
  // mの上限が30万ということは、int型に入りきらない可能性があるのでlong long型にしておく
  long long result = 1LL*m*(m-1)/2;

  //////////////////// 処理 ////////////////////

  // 各辺についてa+bをnで割った余りを求める
  // 各余りになるものがいくつあるか数えておく
  vector<int> counters(n);
  for (int i=0; i<m; i++) {
    counters.at((a.at(i)+b.at(i))%n)++;
  }

  // それぞれ、同じ余りになる組がいくつあるか求め、引いていく
  // 30万本全部平行だとint型に入りきらないのでlong long型にしておく
  for (int num : counters) {
    result -= 1LL*num*(num-1)/2;
  }

  //////////////////// 出力 ////////////////////

  cout << result << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}

Submission Info

Judge Result