Número de unidad de plazas que cumplen una determinada línea diagonal segmento en más de un punto

Question

Vamos $l$, $b$ ser enteros positivos. Dividir el $l \times b$ rectángulo en $lb$ unidad de plazas en la forma habitual. Considerar una de las dos diagonales del rectángulo. Cuántas de estas unidades de plazas contiene un segmento de positivos longitud de la diagonal?

Answer 1

La línea diagonal que va de la cruz $b$ plazas (en el $b$ dirección) y $l$ plazas (en la ($l$ dirección), Estos ($b$$l$ direcciones) se tendrá en cuenta por separado hacia el número total de plazas de la corte, excepto para $\gcd(l,b)$ ocasiones cuando la diagonal hace que la transición de una fila a la siguiente en ambas direcciones a través de un punto de la rejilla. Esta cuenta el inicio/final de las esquinas como "la mitad de un punto de la cuadrícula", por analogía con el $2b \times 2l$ rectángulo.

Así, el número total de plazas con una porción de la diagonal se $l+b-\gcd(l,b)$.

Para la ilustración, $l=8, b=12$ y la diagonal que pasa por $\gcd(12,8)=4$ cuadrícula de puntos para un total de $12+8-4=16$ plazas corte.

Answer 2

Llamar al número solicitado $f(l,b)$, y poner $d=\gcd(l,b)$, uno ha $f(l,b)=d f(\frac ld,\frac bd)$. Esto es debido a que el corte de la diagonal de a $d$ trozos de igual longitud, la subdivisión de los puntos de celosía puntos (de hecho, son precisamente el entramado de puntos en la diagonal), y todos los $d$ piezas son similares.

Esto reduce el problema para el caso en que $l,b$ son relativamente primos. Ahora, no hay intermedio de celosía puntos, así que cada vez que la pases en diagonal en una nueva plaza, o bien lo hace de manera horizontal o vertical, pero no tanto. Ahora uso el hecho de que pasar a una nueva plaza horizontalmente $l-1$ veces en todos los, y verticalmente $b-1$ veces en total. Que hace para $1+(l-1)+(b-1)=l+b-1$ plazas en total, la inicial de $1$ a contar de la plaza es uno es antes de pasar a una nueva plaza para la primera vez.

Para el caso general, entonces uno encuentra $$f(l,b)=d f(\frac ld,\frac bd)=d(\frac ld+\frac bd-1)=l+b-d, \qquad\text{where $d=\gcd(l,b)$.} $$