LuoguP7094 [yLOI2020] 金陵谣 题解
Content
有 \(t\) 组询问,每组询问给定四个整数 \(a,b,c,d\),请求出满足
\]
的正整数对 \((x,y)\) 的个数。
数据范围:\(0\leqslant t\leqslant 20,1\leqslant a,b,c,d\leqslant 10^6,d\times c\leqslant 10^6\)。
Solution
提示性很强的一道题目。
我们先来尝试化简一下这个式子:
两边同时乘以 \(xcy\),得 \(acy+bxy=dcx\)。
把含有 \(x\) 的项移到左边,得到 \(bxy-dcx=-acy\)
整理可得 \((dc-by)x=acy\)
\(\therefore x=\dfrac{acy}{dc-by}\)
化简到这里应该可以明白了:我们从小到大枚举 \(y\),看是否有 \(acy\mod(dc-by)=0\),如果满足的话必然会存在整数 \(x\)。
下界显然是 \(1\),但是如何确定 \(y\) 枚举的上界呢?
让我们再来看看题目:
……满足 \(\dfrac{a}{x}+\dfrac{b}{c}=\dfrac{d}{y}\) 的正整数对 \((x,y)\) 的个数。
……\(1\leqslant a,b,c,d\leqslant 10^6\)。
是否发现了什么?
题目中限制了 \(x,y,a,b,c,d\) 均为正整数!
而又因为 \(acy\) 必然是正整数,所以想要让 \(x\) 为正整数,必然要满足 \(dc-by\) 的结果也是个正整数才行,也就是 \(dc-by>0\)。
再以 \(y\) 为主元化简这个不等式:
\(-by>-dc\)
\(\therefore y<\dfrac{dc}{b}\)。
这下你应该就明白了。
但是!这里会出现一个 bug:当 \(\dfrac{dc}{b}\) 的结果是一个整数的时候,枚举的时候就不能够枚举到 \(\dfrac{dc}{b}\)。理由很容易想通。
所以,我们应当分类讨论一下上界:
- 当 \(b\mid dc\) 的时候,上界就是 \(\dfrac{dc}{b}-1\)。
- 否则,上界就是 \(\dfrac{dc}{b}\)。
以为我是在胡闹?再看题目:
……\(d\times c\leqslant 10^6\)。
好的,现在可以保证这样枚举不会爆炸了。于是就可以愉快地枚举了。
Code
int t, a, b, c, d;
int main() {
t = Rint;
while(t--) {
a = Rint, b = Rint, c = Rint, d = Rint;
int ans = 0;
F(y, 1, d * c / b - (!((d * c) % b) ? 1 : 0)) {
if(1ll * d * c - 1ll * b * y == 0) continue; //该行可省略
if(!((1ll * a * c * y) % (1ll * d * c - 1ll * b * y)))
ans++;
}
printf("%d\n", ans);
}
return 0;
}
最新文章
- Android studio:Groovy 与 Gradle 基础【三】
- OpenCV播放视频带滚动条(3)
- 【OpenCV】图像的遍历
- 【Selenium2+Python】常用操作
- Linux Shell编程变量赋值和引用
- Oracle11g服务及实例
- ThinkPad x200为何总是CPU占用50%
- windows rt 扫描二维码
- datatables里面的search怎么去掉?
- Mybatis 源码学习系列
- 深度理解PHP中for与foreach两个循环结构遍历数组的区别
- Android精通教程-第一节Android入门简介
- openssl:AES CBC PKCS5 加解密 (C/GOLANG)
- Java可视化编程---SendMail工具的开发
- 跟老齐学Django 项目实战笔记
- x+y+z=n的正整数解
- HTML5移动应用左右滑动touchmove touchmove touchend 实例
- graphql-binding openapi 集成demo
- RxSwift 系列(四)
- springmvc+shiro认证框架配置
热门文章
- ppt的作用
- 使用微软RPA工具 Power Automate自动完成重复性工作
- P7045 「MCOI-03」金牌
- P2336 [SCOI2012]喵星球上的点名(SA+莫队)
- Codeforces 1513F - Swapping Problem(分类讨论+乱搞)
- 毕业设计压力测试——jmeter
- 睡眠或者重启windows,无法ssh连接或者pingVMware的虚机
- rabbit mq的安装
- 日常Java 2021/10/26
- A Child&#39;s History of England.21