F x?y?n!

比赛安排(PDF题面存放于本题)

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

题目:给一个整数n,在满足 gcd(𝑥,𝑦)=𝑛,𝑥≠𝑦且1≤𝑥,𝑦<263的基础上,使得x⊕y最小。

知识点:数学

思路:

首先x=na,y=nb,gcd(a,b)=1,|a-b|>=1,因为n|a-b|>=n,即|x-y|>=n,又因为|x-y|<=x⊕y,所以x⊕y的最小值为n。(光算样例也能得到) 如何保证x⊕y的最小值为n?因为n(1≤n<2 31),所以我们创造一个k为n左移位31位,x=nk,y=nk+n,这样左移位的值归零,只剩下y后的n.

代码:

using namespace std;
#define int long long 
void slove() {
    int n; cin>>n;
    int k=1LL<<31;
    int x,y;
    x=n*k;
    y=n*(k+1);
    cout<<x<<' '<<y<<endl;
}
signed main() {
    int t;cin>>t;
    while(t--) {
        slove();
    }
}
全部评论

相关推荐

点赞 评论 收藏
分享
01-30 22:03
门头沟学院 Java
用微笑面对困难:我滴妈,【俩月】【实习】【主管】仨debuff吃满了,独立设计开发的项目写了绝大占比的运营板块,你独立开发,那维护、问题复盘、日志更新、bug、策划书全是自己整的? 不建议写那么大,可以从小出发更容易
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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