/ 注册

去牛客

竞赛讨论区 > 关于F题的讨论

Dr_ZhangEQ

发布于 02-06 01:01 北京

+ 关注

关于F题的讨论

F题题解有误，题解试图证明当 $\gcd(x,y) = n$ 时， $x \oplus y$ 是 $n$ 的倍数，从而得出 $x \oplus y \ge n$ 的结论。这是显然有问题的，考虑令 $x = 3, y = 6$ ，则有 $\gcd(3,6) = 3$ ，而 $3 \oplus 6 = 5$ ，并不是 $3$ 的倍数。

下面给出个人的证明 $n$ 为最小值的方法

不妨设 $y > x$ ，则有 $y = x + kn$ ，其中 $k \ge 1$

设 $x \oplus y = t$ ，代入得 $x \oplus (x + kn) = t$

利用异或的性质得， $x + kn = x \oplus t$ ，而 $x \oplus t = x + t - 2(x \& t)$

于是有 $t = kn + 2(x \& t)$ ，显然 $x \& t \ge 0$ 且 $kn \ge n$

从而有 $t \ge n$

利用该方法，我们也能轻易想到如何构造最小值，即满足 $k = 1$ 且 $x$ 是 $n$ 的倍数且 $x \& n = 0$ ，此时显然合法，因为 $\gcd(x,x+n) = n\gcd(\frac{x}{n},\frac{x}{n}+1) = n$

于是只需要令 $x = n << (\log_2(n) + 1)$ ， $y = x + n$ 即可

2026最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

全部评论

(1) 回帖

加载中...

话题同步到我的动态回帖

返回全部帖子

本文相关内容

等你来战

查看全部

蓝桥杯多校模拟赛（第二场）

报名截止时间：2026-04-06 17:00
牛客小白月赛131

报名截止时间：2026-04-10 21:00
2026年浙江工业大学之江学院程序设计竞赛

报名截止时间：2026-04-11 16:00
北华大学第十三届大学生程序设计竞赛(同步赛)

报名截止时间：2026-04-12 18:00
牛客周赛 Round 139

报名截止时间：2026-04-12 21:00
牛客练习赛151

报名截止时间：2026-04-17 21:30

热门推荐

扫描二维码，关注牛客
意见反馈
下载牛客APP，随时随地刷题

牛客竞赛，专业的竞技算法训练平台: 扫描二维码，进入QQ群



扫码关注“比赛自动姬”

公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
牛客科技© All rights reserved admin@nowcoder.com
京ICP备14055008号-4 增值电信业务经营许可证营业执照人力资源服务许可证
京公网安备 11010502036488号