二分乱搞过题 || solution - CF2039C2

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

CPP

#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;
}

二分乱搞过题 || solution - CF2039C2

文章操作

Solution

Code

相关推荐

评论

二分乱搞过题 || solution - CF2039C2