WLOG we can just consider x, y > 0. A coordinate (x, y) is visible if and only x and y are relatively prime. So for each x coordinate, we want to compute the number of y s that are relatively prime to x in the range .

We can use inclusion-exclusion to count everything that shares at least one factor with x and subtract these from the range. First we count all multiples of p where p is some prime factor of x. But this double-counts multiples of pq, so we subtract all multiples of pq. And then we add back multiples of pqs, and subtract multiples of pqst, and so on. So the total runtime is around

Where ω(x) is the number of distinct prime factors of x. One piece of number-theoretic intuition is that ω(x) grows extremely slowly (max_{x ≤ 1000000}{ω(x)} = 7), and most elements in the range only have  ≤ 3 distinct prime factors. So this is fast enough in practice. (You can just run the maximal case to make sure.)

Auto comment: topic has been updated by choice (previous revision, new revision, compare).

I used to write binary search like this:

int binsearch(vector<int> & x, int k)
{
  int i = 0;
  for(int d = 1<<N; d; d /= 2)
    if(i + d < x.size() && x[i + d] <= k)
      i += d;
  return a;
}

One cute way of solving C without using the "shape" array is to define a spiral of size 1 as simply a single square. The recurrence then follows quite naturally for larger spirals.