Div1 500 RightTriangle

SRM

問題

Pn＝(a*n2＋b*n+c) mod places (0≦n＜points) を定める．円周に places 個の点を等間隔に取り，Pn 番目の点を赤く塗る．塗ろうとしている点が既に赤い場合は赤くない点が出るまで次を探ってとにかく塗る．
その作業後，赤い点から3点を選び三角形を作った場合，直角三角形はいくつできるか？

考え方

円周の点を結んで直角三角形をつくる必要十分条件は三角形の一辺が直径になってること．なのでまず赤い点を組み合わせて直径がいくつ取れるか数える．それに対して直径以外の n-2 点へ線を繋げると必然直角三角形になるので求める組み合わせは (直径の数)×(点の数−2) になる．

コード

#include <vector>
#include <algorithm> 
using namespace std; 
typedef long long lint; 

class RightTriangle 
{ 
public: 
  lint triangleCount(int MOD, int N, int a, int b, int c) 
  { 
    if( MOD & 1 ) return 0;
    vector<int> red;
    for( lint i = 0 ; i < N ; ++i )
      red.push_back(((a * i + b) % MOD * i + c) % MOD);

    while( true ) {
      for( int i = 0 ; i < N ; ++i ) red[i] %= MOD;
      sort(red.begin(), red.end());
      bool noChange = true;
      for( int i = 1 ; i < N ; ++i )
        if( red[i-1] >= red[i] ) {
          red[i] = red[i-1] + 1;
          noChange = false;
        }
      if( noChange ) break;
    }

    const int MOD2 = MOD / 2; 
    int j;
    for( j = 0 ; j < N && red[j] < red[0] + MOD2 ; ++j ) ;
    lint cnt = 0; 
    for( int i = 0 ; i < N && red[i] < MOD2 ; ++i ) {
      while( j < N && red[j] < red[i] + MOD2 ) ++j;
      if( j < N && red[j] == red[i] + MOD2 ) ++cnt;
    } 
    return cnt * (N - 2);
  } 
};