Un punto lattice $(x, y)$ en el primer cuadrante ($x, y0$ son números enteros mayores o iguales a 0), que no sea el origen, es visible desde el origen si la línea de $(0, 0)$ a $(x, y)$ no pasa a través de cualquier otro punto lattice. Escriba un programa que, dado un valor para el tamaño $N$ ($1 ≤ N ≤ 1000$), calcula el número de puntos visibles $(x, y)$ con $0 <= x, y <= N$.

Para resolver este problema trazaremos las rectas (imaginariamente) desde todos los puntos que pueden existir en la cuadrícula hacia el origen. Dichas rectas, además de pasar siempre por el origen, la coordenada $(x_2 = 0, y_2 = 0)$, también deberán pasar por el punto $(x_1 = x, y_2 = y)$ donde $0 ≤ x, y ≤ N$. Recordemos la ecuación de la recta: $(x_2 - x_1) / (y_2 - y_1) + b$, por tanto para nuestras rectas la ecuación se reducirá a $x / y$.
Podemos ver que algo sucede con los puntos que no son visibles, y es que la recta que los une puede ser expresada por un múltiplo de la recta de uno que si es visible. El caso más sencillo: tomando el punto visible $(1, 1)$ y el punto no visible $(3, 3)$, tenemos que las coordenadas del punto no visible es tan solo $(3 * 1) / (3 * 1)$, la forma para identificar esto es obtener el MCD de $x$ y $y$, mientras que para el punto visible $MCD(x, y) = 1$, para el no visible $MCD(x, y) > 1$.

Ahora solo hay que obtener todos los puntos dentro de nuestra cuadrícula cuyo MCD sea igual a 1 para cada consulta que nos hagan. Esto es sencillo pero es un gasto inecesario de recursos, por lo que lo mejor es realizar un precálculo partiendo de que para $N = 0$ la respuesta es $0$ y para $N = 1$ la respuesta es $3$. Otro punto a considerar es que podemos solo calcular la mitad de los puntos ya que los puntos son simétricos.

a[0] = 0;
a[1] = 3;
for(int x = 2; x <= 1000; x++){
 int sum = 0;
 for(int y = 1; y < x; y++){
  if(mcd(x,y) == 1) sum++;
 }
 a[x] = a[x-1] + 2 * sum;
}