SRM473 Div1 Medium

500

円の中心を通るような直線を含む三角形は直角三角形になる。

a = 0, b = 0 のときが問題で、愚直にやると O(N^2) かかる。
気のきいた方法を取るべし。

通した後で気付いたけど、set.lower_bount でいいのでは。

const int N = 1000000 + 1;
int next[N];
bool vis[N];

int get_next(int n)
{
  if (!vis[n]) return n;
  else {
    return next[n] = get_next(next[n]);
  }
}

int put_red(int n)
{
  int m = get_next(next[n]);
  vis[m] = true;
  return m;
}

void init(int m)
{
  for (int i = 0; i < N; ++i) {
    vis[i] = false;
    next[i] = (i + 1) % m;
  }
  return ;
}

class RightTriangle {
public:
  long long triangleCount(lli places, lli points, lli a, lli b, lli c)
  {
    if (places % 2) return 0;
    init(places);

    set<lli> s;
    for (lli i = 0; i < points; ++i) {
      int n = (a * i * i + b * i + c) % places;
      s.insert(put_red(n));
    }
    lli ret = 0;
    for (int i = 0; i < places / 2; ++i) {
      int j = (i + (places / 2)) % places;
      if (s.count(i) && s.count(j)) {
        ret += points - 2;
      }
    }
    return ret;
  }
}