小 S 的 ARC191 参赛记-2

· · 题解

前序：小 S 的 ARC191 参赛记-1（即 ARC191A 题解）

切掉了 A 后，小 S 十分愉快地开了 B。

大致题意

给定 n,k，求第 k 大的 满足 x\bmod n=x\oplus n 的 x，无解输出 -1，多测。

小 S 看到这道题也是十分兴奋啊，想了一下立马口胡了个结论：

因为这是题解不是赛时，所以小 S 还是要证一下的。

首先，x<n 时，原式变为 x=x\oplus n，很明显当且仅当 n=0 时成立，而 n 显然不能为 0。

其次，如果 x 二进制下的最高位高于 n 二进制下的最高位时，那么有 x\oplus n>n（因为 x 二进制下的最高位会被保留），而 x\bmod n<n，所以原式不成立。

那么，因为 x\ge n 且 x 的二进制下的最高位不高于 n 二进制下的最高位时，所以有 n\le x<2\times n，则 x\bmod n=x-n。

那也就是说，如果 n 在二进制下某位是 1，则 x 在二进制下这位也必须是 1，不然无法实现 x-n=x\oplus n。

小 S 高兴的不得了，因为他发现，这意味着 x 在二进制下，可以自由变化的那些位置，恰好就是 n 的二进制下不大于最高位的、值为 0 的位数。设这样的位数有 sum 个，则有 2^{sum} 个不同的 x。

至于如何计算第 k 大的 x，将 k-1 二进制拆分之后一位位填到 sum 个自由位上去就可以了。

于是小 S 愉快地无伤通过了此题，真是与 ARC189B 的 -10 截然不同的结局啊。

也许，这就是小 S 每天殷切地对着卫星许愿的原因吧。

S.A.T.E.L.L.I.T.E.

（但是小 S 还是被 C 的神秘结论创飞了）

Code

#include<algorithm>
#include<bitset>
#include<deque>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<utility>
#include<vector> 
#include<chrono>
#include<random>
#include<tuple>
#include<unordered_map>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define debug1(x) cerr<<#x<<"="<<x<<" "
#define debug2(x) cerr<<#x<<"="<<x<<"\n"
const int inf=1e16,maxn=1e6+10;
namespace ARIS2_0{
    void solve(){
        int n,k;cin>>n>>k;
        vector<int>v;
        for(int i=0;(1ll<<i)<=n;i++){
            if(!((n>>i)&1))v.push_back(i);
        }
        if(k>(1ll<<(v.size()))){
            cout<<"-1\n";
            return;
        }
        int ans=n;
        k--;
        for(int i=0;i<v.size();i++){
            if((k>>i)&1){
                k-=(1ll<<i);
                ans+=(1ll<<(v[i]));
            }
        }
        cout<<ans<<"\n";
    }
}
signed main(){
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;cin>>t;
    while(t--)ARIS2_0::solve();
    return 0;
}
/*
clang++ -std=c++14 -Wall -Wextra -Wshadow -Wconversion -Wl,-stack_size -Wl,512000000
*/