二分乱搞过题 || solution - CF2039C2

littlebug · 2024-12-07 23:26:50 · 题解

Solution

设 t 为 x 的最高二进制位的上一位为 1，其它位为 0 所组成的数。然后发现若 y \ge t，则不可能存在 y ~|~ x \oplus y，于是可以先把 < t 的部分枚举出来。对于 \ge t 的部分由于只有 x \oplus y 为 x 的倍数时才可以。

显然暴力枚举是不行的，那这个 y 如何统计呢？

通过写了一个暴力，我们发现满足条件的 y 看起来好像有单调性（合法性形如 1,1,1,\ldots,0,0,0，但中间可能出现一些前 0 后 1 的情况）！所以可以二分，然鹅这个单调性并不怎么优秀，得到结果后判一下前十个后十个数即可。

然后就这样二分乱搞过了。

Code

#include<iostream>
#include<cstdio>
#include<bitset>

#define int long long
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rpe(i,a,b) for(int i=(a);i>=(b);--i)

using namespace std;

int x,m;

il int gm(int x)
{
    int ans=0;
    while(x) ++ans,x>>=1;
    return (1ll<<ans)-1;
}

il bool check(int mid)
{
    return (x^mid)<=m;
}

il void solve(int __Ti)
{
    cin>>x>>m;

    if(m<=x*2)
    {
        int cnt=0;
        rep(i,1,m) ((x^i)%x==0 || (x^i)%i==0) && (++cnt,1);
        return cout<<cnt<<'\n',void();
    }

    int t=gm(x);

    int cnt=0;
    rep(i,1,t) ((x^i)%x==0 || (x^i)%i==0) && (++cnt,1);

    int l=1,r=m/x+100,mid=-1;
    while(l<r)
    {
        mid=l+r+1>>1;
        check(x*mid) ? (l=mid) : (r=mid-1);
    }

    cnt+=l-1;
    rpe(i,l,max(l-10,1ll)) !check(x*i) && (--cnt,1);
    rep(i,l+1,l+10) check(x*i) && (++cnt,1);

    cout<<cnt<<'\n';
}

signed main()
{
    ios::sync_with_stdio(0); ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
    int __T; cin>>__T; rep(__Ti,1,__T) solve(__Ti);
    return 0;
}