Ciyeblog
Ciyeblog
首页
关于
友链
博主的话
随笔
gcd(x,y)=1，l<=x,y<=r，求x,y使得|x-y|最大
于
2025-01-12
由 ciye 发布
相关题目：[Problem - D - Codeforces](https://codeforces.com/contest/2043/problem/D "Problem - D - Codeforces") 解法：从大到小枚举x,y距离len（即|x-y|），然后判断gcd(x,x+len)是否==1，若==1则求出解直接return。这种方法比直接双重for循环遍历x,y快，虽然两者时间复杂度都是O(n^2)，但由于该方法是直接从len大到len小遍历的，相当于提前确定len值，找到结果能提前结束，并且找到两个距离为len的互质数又比较好找，所以跑得比较快；而双重for直接遍历不确定len值，需要完全遍历才能找到最大len值，相当于硬生生跑完了O(n^2)的复杂度，所以较慢。 写法： for(int len=r-l;len>=0;len--) { for(int i=l;i<=r-len;i++) { if(gcd(x,x+len)==1) } }
分类：
默认分类
标签：
无标签
暂无评论
发表评论
取消回复
提交评论
×