Codeforces Round #843 (Div. 2) C Interesting Sequence

绝地灬酷狼 2024-03-30 17:31 79阅读 0赞

[Problem - C - Codeforces][]

题意：

给定n和x，求最小的m使得：

![0e0d1d8e52c5874275573ed2ba3637ad.png][]

n和x范围是1e18

思路：

看到1e18，要不就是打表找规律，要不就是O(1)，要不就是O(logn)

因为这题是bitmask，因此按位考虑，是O(logn)的

**让我们凭空求m，要不枚举，要不二分，要不直接求**

枚举肯定不行

二分的话不能维护区间与的结果

因此我们根据n和x的位表示直接求m

![33b3849ade46b2632be7818f5e8af155.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    int n,x;
    void solve(){
        cin>>n>>x;
        bitset<64> b1(n),b2(x);
        int l=n,r=5e18;
        for(int i=63;i>=0;i--){
            if(b1[i]==0&&b2[i]==0) continue;
            else if(b1[i]==0&&b2[i]==1){
                cout<<-1<<'\n';
                return;
            }else if(b1[i]==1&&b2[i]==1){
                r=min(r,(n/(1ll<<i)+1)*(1ll<<i)-1);
            }else{
                l=max(l,(n/(1ll<<i)+1)*(1ll<<i));
            }
        }
        if(l<=r) cout<<l<<'\n';
        else cout<<-1<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1775/problem/C
[0e0d1d8e52c5874275573ed2ba3637ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9aaeec1ef2294b65bdb9e6c3d2b858c9.png
[33b3849ade46b2632be7818f5e8af155.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2dcf739483724d74a85f1aa3fd5b5fa4.png

发表评论取消回复

表情：

评论列表（有 0 条评论，79人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #843 (Div. 2) C Interesting Sequence

[Problem - C - Codeforces][] 题意：给定n和x，求最小的m使得： ![0e0d1d8e52c5874275573ed2ba3637ad.pn

绝地灬酷狼/ 2024年03月30日 17:31/ 0 赞/ 80 阅读

相关【构造】Codeforces Round #843 (Div. 2) B Gardener and the Array

[Problem - B - Codeforces][] 题意：给定一个序列，让你判断是否存在两个子序列使得这两个子序列或起来相等思路：设两个子序列是a和b 两

女爷i/ 2024年03月30日 17:28/ 0 赞/ 68 阅读

相关 Codeforces Round #708 (Div. 2) C1 C2

[Problem - C1 - Codeforces][] 题意：让你构造三个数，使它们加起来是n，然后lcm(a1,a2,a3)<=n/2 思路：构造题，要满足两

古城微笑少年丶/ 2024年03月29日 14:25/ 0 赞/ 87 阅读

相关 Codeforces Round #729 (Div. 2) c题

[https://codeforces.com/contest/1542/problem/C][https_codeforces.com_contest_1542_proble

向右看齐/ 2022年10月12日 05:25/ 0 赞/ 201 阅读

相关 Codeforces Round #728 (Div. 2)a-c

https://codeforc.es/contest/1541 cf a b c a 给定一个数n，1 2 3 4 … n

比眉伴天荒/ 2022年10月10日 04:48/ 0 赞/ 38 阅读

相关 Codeforces Round 374 div2

题目链接： [ CodeforcesRound374][CodeforcesRound374] 做了这么久cf了，，c题有时候还是做不起，，真的好菜，，，，

Dear 丶/ 2022年07月16日 03:38/ 0 赞/ 199 阅读

相关 Codeforces Round #118 (Div. 2) C. Plant

Dwarfs have planted a very interesting plant, which is a triangle directed "upwards". Th

蔚落/ 2022年05月17日 01:13/ 0 赞/ 222 阅读

相关 Codeforces Round #553 (Div. 2)

A：[http://codeforces.com/contest/1151/problem/A][http_codeforces.com_contest_1151_proble

た入场券/ 2021年11月04日 13:36/ 0 赞/ 283 阅读

相关 Codeforces Round #573 (Div. 2)

<table> <thead> <tr> <th>Sloved</th> <th align="center">A</th> <th alig

浅浅的花香味﹌/ 2021年09月29日 13:10/ 0 赞/ 293 阅读

相关 Codeforces Round #643 (Div. 2) Sequence with Digits【思维】题解

目录 1.题目 2.题意 3.思路 4.代码 1.题目 Le

系统管理员/ 2021年07月24日 15:06/ 0 赞/ 324 阅读