CF1041B Buying a TV Set 题解
2024-08-27 13:10:40
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));
}
最新文章
- tiny4412学习一:编译uboot,体验裸机
- Hadoop on Yarn 各组件详细原理
- 一天天的sql总结
- Leetcode--Add two number
- FreeModbus Slave 改进的eMbPoll()【worldsing 笔记】
- C#递归搜索指定目录下的文件或目录
- Shell基础一
- 处理input标签的border-radius
- 201521123038 《Java程序设计》 第五周学习总结
- 智能优化算法对TSP问题的求解研究
- [置顶]生鲜配送管理系统_升鲜宝V2.0 销售订单汇总_采购任务分配功能_操作说明
- IntelliJ IDEA 2017新工具
- 第56节:ArrayList,LinkedList和String
- Docker在windows下的使用【二】
- jQuery - 字符串与json对象之间的转换
- 潭州课堂25班:Ph201805201 第九课 函数作用域和匿名函数 (课堂笔记)
- Sitecore CMS中查看标准字段
- Redis进阶实践之三如何在Windows系统上安装安装Redis(转载)
- 登录mysql出现/var/lib/mysql/mysql.sock不存在
- 先做一个用来测试的chrome浏览器插件