牛客2 F

x?y?n!

https://ac.nowcoder.com/acm/contest/120562/F

关于这道题,首先介绍异或运算,简单来说就是给两个数字,把他们变成二进制,然后进行相减,是每一位单独相减,然后得到绝对值,例如: 0 1 0 1 0 0 1 1 ,得到: 0 1 1 0 所以x+y>=x异或y>=x-y,所以x异或y最小等于x-y,另外n是x,y的最大公约数,那么,设x=an,y=bn,那么a,b一定互质,如果不是互质,那么n就不是最大的公约数了,而是n的一个倍数是最大公约数,所以x-y最小是为多少呢,是n,例如5n-4n=n 然后,值得注意的是这题的数据范围,1≤𝑛<2的31次方,1<=x,y<=2的63次方,31*2<63,不觉得很神圣吗,另外x,y都为n的倍数,设x为y的倍数,我们要知道,在二进制中只要....比较难表达吧,反正如果数字一样,但是位数更多,就一定是倍数,例如1111 和 11110000,如果我把1111当成n,再来一个11111111,就可以满足题目所有要求了。所以其实就是要做到x异或y等于n

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        long long n;
        cin>>n;
        cout<<(n<<31)<<" "<<((n<<31)+n)<<endl;//位移31位
        
    }
    
    return 0;
}

全部评论
另外有人会用|这个运算符,不过优先级上:+大于<<大于|,另外|是只有被|的数字对应的某一位为0时,才回加上n的那一位的数字,这题是差不多的
点赞 回复 分享
发布于 02-13 01:41 江苏
为什么我会想到这件事情,因为我也疑惑过
点赞 回复 分享
发布于 02-13 01:26 江苏
可能会有人疑惑,a和b这两个数字要求互质,你就这么确定,你这样构造能互质吗,我们来看看, 设n为10101,x为1010110101,y为1010100000。 首先y为n的2的5次方的倍数,x其实就是n+y,所以在二进制的特殊情况下,y一定是n的偶数倍,而x是n的(偶数+1)倍,奇数跟偶数当然是互质
点赞 回复 分享
发布于 02-13 01:22 江苏

相关推荐

当年还在美团那个倒霉的&nbsp;Peppr&nbsp;团队工作时,我一直有个疑问:这群人每天到底在自嗨什么。每次开会一堆人围着一堆“看起来很高级”的文档转,模板统一、名词复杂、页数感人,每一页都在暗示一件事:“你不懂,是因为你不专业。”但现实是——代码照样写在&nbsp;💩&nbsp;山上,该出问题还是会出问题,这真的很逗,系统一出问题,文档的唯一作用就是证明:“我们当初确实认真写过文档。”所以本质区别到底是什么?是代码质量提升了,还是大家在精神层面完成了一次“工程师&nbsp;cosplay”?有句话说得好潮水退去才知道谁在裸泳。还记得当时的马哥、明哥(图&nbsp;1&nbsp;左)最爱反复强调一句话:“所有场景一定要想到。”、“这个场景为什么没考虑到?”不过他们这些话我是真的听进去了。不然我也不会在一年多前就说:这个项目活不过两年。顺带一提,那段时间还有个固定节目。每次下楼,总能听见我明哥在吐槽不同的人。我从他身后绕过去,经常能听到他一边抽烟一边说:“xx&nbsp;这小子太坑了,回头我一定要跟马哥说说。”于是深谙人情世故但真不会抽烟的我也会从口袋掏出一支低尼古丁含量的烟给自己点上,假意自己什么都没听到什么都不知道,只是来抽烟的。后来我才明白,这可能也是团队文化的一部分:问题永远在别人身上,而我们,永远在复盘里😂。
秋招白月光
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务