说真的这很显然吧。
by p_Hydroxy @ 2023-11-07 11:53:10
兔八哥与猎人那道题底下题解好像有证明的
by p_Hydroxy @ 2023-11-07 11:54:04
~~这不显然吗~~
by GoldenFishX @ 2023-11-07 11:56:21
修正：线段非段中间整点数目为 `gcd(a-x,b-y)-1`。
证明：只需考虑另一端点 $(x,y)=(0,0)$ 的情况，此时线段所在直线方程为 $ay=bx$，即需解出满足 $0<x<a,0<y<b$ 的所有解，相当于 $0<x\leqslant a,0<y\leqslant b$ 的情况的解 $-1$。
对于$0<x\leqslant a,0<y\leqslant b$ 的情况：
如果 $a,b$ 互质，那么只当 $x=a,y=b$ 时成立，解个数为 $1$。
如果不互质，得到 $1\neq g=\gcd(a,b)$，两边同除 $g$，得到 $\dfrac{a}{g}y=\dfrac{b}{g}x$，显然 $\gcd\left(\dfrac ag,\dfrac bg\right)=1$，$0<x\leqslant\dfrac{a}{g},0<y\leqslant\dfrac bg$ 解个数为 $1$，但是我们因此找到了 $g$ 段这样的线段，于是 $0<x\leqslant a,0<y\leqslant b$ 的解个数是 $g$。
综上解的个数是 $\gcd(a,b)-1$。
by Terrible @ 2023-11-07 12:06:35
@[p_Hydroxy](/user/551788) @[Big_Caibi](/user/156353) 反正我试了试，没有完全证出来。。。。而且这个式子看起来不是那么显然啊？
by Kniqht @ 2023-11-07 12:44:20
@[Terrible](/user/195942) 谢谢orz
by Kniqht @ 2023-11-07 12:44:42
@[Kniqht](/user/315205) 画个图就显然了啊
by p_Hydroxy @ 2023-11-07 12:54:55