题解：P14628 [2018 KAIST RUN Fall] Fractions

· · 题解

因为要求约分后的分子分母都不超过 $1000$，所以用 $1000^2$ 的复杂度枚举约否后的结果 $\dfrac ab$（$\gcd(a,b)=1$）。然后需要计算有多少 $k$ 满足 $ak \le n$ 且 $bk \le m$。显然答案是 $\min(\lfloor n/a \rfloor, \lfloor m/b \rfloor)$。