题解 P7094 【[yLOI2020] 金陵谣】
一只书虫仔
·
·
题解
yLOI 2020 A 前排膜拜扶咕咕
Description
给定 a,b,c,d，求有多少组正整数 x,y 满足：
\dfrac{a}{x}+\dfrac{b}{c}=\dfrac{d}{y}
Solution
这个第一个测试点是什么鬼
爆推柿子：
$$\begin{aligned}\dfrac{a}{x}+\dfrac{b}{c}=\dfrac{d}{y}&\to\dfrac{ac}{cx}+\dfrac{bx}{cx}=\dfrac{d}{y}\\&\to \dfrac{ac+bx}{cx}=\dfrac{d}{y}\\&\to dcx=y(ac+bx)\\&\to dcx=acy+bxy\\& \to dcx-bxy=acy\\& \to (dc-by)x=acy\end{aligned}$$
既然要保证 $x,y$ 是正整数，那么就需要保证 $dc>by$，也就是：
$$\begin{aligned}dc>by &\to by<dc\\&\to y<\dfrac{dc}{b}\end{aligned}$$
也就是说，框定了 $y$ 的枚举范围 $\left[1,\dfrac{dc}{b}\right)$，然后进行，枚举即可。