CF1041B Buying a TV Set 题解

Content

给定四个数 \(a,b,c,d\)，求满足以下条件的数对 \((x,y)\) 的个数：

• \(x\leqslant a,y\leqslant b\)。
• \(\dfrac{x}{y}=\dfrac{c}{d}\)。

数据范围：\(1\leqslant a,b,c,d\leqslant 10^{18}\)。

Solution

众所周知，数据范围很大的话一般就得要推结论了。

我们先把这个 \(\dfrac{c}{d}\) 化简一下，假设是 \(\dfrac{c’}{d’}\)。由于很明显，\(x,y\) 显然要分别是 \(c’,d’\) 的倍数，所以设 \(x=k_1c’,y=k_2d’\)，那么我们由上面的条件：

\(x\leqslant a,y\leqslant b\)

\(\Rightarrow k_1c’\leqslant a,k_2d’\leqslant b\)

\(\Rightarrow k_1\leqslant \dfrac{c’}{a},k_2\leqslant \dfrac{d’}{b}\)

又因为 \(\dfrac{x}{y}=\dfrac{c’}{d’}\)

所以 \(\dfrac{c’}{x}=\dfrac{d’}{y}\)

那么就只能够从 \(k_1,k_2\) 中取较小值了。因此答案就是 \(\min\{\dfrac{c’}{a},\dfrac{d’}{b}\}\)。

Code

long long a, b, c, d;int main() {
scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
long long gcdcd = __gcd(c, d);
c /= gcdcd, d /= gcdcd;
printf("%lld", min(a / c, b / d));
}