P3951 小凯的疑惑
2024-09-05 06:42:53
P3951 小凯的疑惑
题解
题意也就是求解不能用 ax+by 表示的最大数 ans(a,b,x,y,都是正整数)
给定 a ( =7 ) , b ( =3 )
我们可以把数轴非负半轴上的数按照a的剩余类分成a列,如上图
所以 a 的倍数一定可以取到,此时 y=0,那么我们把 a 的倍数这一列划掉
然后我们再考虑 y!=0的情况:
(1)b的倍数一定可以取到,此时 x=0
(2)和b %a 同余的数字一定可以取到,其实就是确定了 y,then确定了by,加上 a 的倍数
所以我们就可以把 b 的倍数以及和它%a同余的数字划掉,表现在图中,也就是:
把b的倍数那一列划掉
最后总会出现 a 和 b 把数轴上的点(除了仅有的几个点)全部覆盖
问题也就是求这仅有的几个点中最大的那一个
当我们把数轴上的数字分成 a 列时,自然会有一列被 a 划掉
还剩下a-1列要被 b 及其倍数划掉
b每扩大一倍,就会覆盖掉一列 ( 因为大前提保证 gcd(a,b)=1 )
那么当 b 扩大到第a-1倍时,就把剩下的所有数字覆盖了
但是 b*(a-1) 这一列中,b*(a-1)上面的那个数字是一定不会被覆盖的,与它同一行的所有数字都会被覆盖掉,所以这个数字就是要求的最大值
ans = b * ( a-1 ) - a
= a * b - a - b
代码
#include<bits/stdc++.h> using namespace std; long long a,b; int main()
{
scanf("%d%d",&a,&b);
printf("%ld\n",a*b-a-b);
return ;
}
最新文章
- AJax登录。。转
- css相对定位和绝对定位
- Android 图片三级缓存
- 从简单需求到OLAP的RANK系列函数
- Unity3d 音效模块相关
- ASP.NET MVC5 网站开发实践
- js 标签云效果
- 【转】IOS中定时器NSTimer的开启与关闭
- SQL 远程过程调用失败【0x800706be】或正在关闭 【0x80041033】解决方法
- LDR伪指令与ADR伪指令的区别
- sqlserver和Windows资源管理器争用内存
- Hibernate基础学习(七)&mdash;检索方式
- 201521123085 《Java程序设计》第8周学习总结
- jdbc连接阿里云服务器上的MySQL数据库 及 数据库IP限制
- AIX详细查看用户/进程使用内存
- 55.UIbutton点击切换颜色
- sdcard 导入文件错误
- Oracle比较2个表内容
- appium 5-27屏幕旋转、
- 数据库中查询json 样式的值的sql语句
热门文章
- ONNX预训练模型加载
- 19.SSM整合_配置式开发
- 数学模块 math 函数的调用
- 异常-Data truncation: Truncated incorrect DOUBLE value: &#39;-9370.3530-&#39;
- sql server 防 注入
- Ajax返回数据却一直进入error(已经解决)
- systemctl可以实现nginx进程挂了之后自动重新启动
- hdu3715 Go Deeper[二分+2-SAT]/poj2723 Get Luffy Out[二分+2-SAT]
- 【洛谷P4430】小猴打架
- 牛客练习赛3 绝对半径 ——k尺取法