嘿，我之前写代码的时候也碰到过类似的问题，咱们一步步拆解，搞清楚怎么解决它：

问题梳理 #

给定两个正整数M和N，我们有两个分数序列：

• 序列A：aₙ = n/N，其中n取1到N-1的整数（比如N=5时，就是$\frac{1}{5}、\frac{2}{5}、\frac{3}{5}、\frac{4}{5}$）
• 序列B：bₘ = m/M，其中m取1到M-1的整数（比如M=8时，就是$\frac{1}{8}$到$\frac{7}{8}$的所有分数）

我们要找的是这两个序列里任意两个元素之间的最小绝对距离，也就是求 $\min(|aₙ - bₘ|)$，其中n的范围是1到N-1，m的范围是1到M-1。

核心解法思路 #

这个问题本质上可以转化为分数差的最小值问题。把两个元素的差写成分数形式：

|n/N - m/M| = |n*M - m*N| / (N*M)

因为分母N*M是固定的正整数，所以要让整个值最小，关键就是让分子|n*M - m*N|尽可能小。这里我们可以结合最大公约数（gcd）来分析：

1. 当N和M的最大公约数g > 1时：
   我们可以把N拆成g*N'，M拆成g*M'，其中N'和M'是互质的（也就是$\gcd(N',M')=1$）。这时候存在整数k（$1≤k≤g-1$），使得n = k*N'，m = k*M'，代入后会发现：

   aₙ = (k*N')/(g*N') = k/g，bₘ = (k*M')/(g*M') = k/g
   

   也就是说两个序列里存在相等的元素，这时候最短距离直接就是0。比如N=6、M=4，$\gcd(6,4)=2$，序列A里的$\frac{3}{6}=0.5$和序列B里的$\frac{2}{4}=0.5$完全相等，距离为0。

2. 当N和M互质（$\gcd(N,M)=1$）时：
   根据贝祖定理，一定存在正整数n（$1≤n<N$）和m（$1≤m<M$），使得n*M - m*N = ±1，这时候分子|n*M - m*N|的最小值就是1，对应的最短距离就是$\frac{1}{NM}$。
   就像你举的例子：N=5，M=8，$\gcd(5,8)=1$，最短距离就是$\frac{1}{58}=0.025$，正好对应$\frac{3}{8}$（0.375）和$\frac{2}{5}$（0.4）的差，以及$\frac{5}{8}$（0.625）和$\frac{3}{5}$（0.6）的差。

最终步骤总结 #

• 第一步：计算g = gcd(N, M)（可以用欧几里得算法快速求解）
• 第二步：如果g > 1，最短距离为0（因为两个序列存在相等元素）
• 第三步：如果g = 1，最短距离为$\frac{1}{N*M}$

备注：内容来源于stack exchange，提问作者Sentry