题解：AT_arc129_a [ARC129A] Smaller XOR

yueyixuan1 · 2026-05-13 13:22:20 · 题解

题意

求有多少个数 x 满足 L \le x \le R，并且 x \oplus N < N。

思路

我们枚举 N 的每一位，如果这一位是 1，那么当然 [2^{i},2^{i+1}-1] 这一个区间都满足 x \oplus N < N，当然以上的区间需要求出在 [L,R] 之内的个数。

时间复杂度 O(\log N)。

核心代码

ll n,l,r;
ll ans=0;

inline void solve(){
    n=read(),l=read(),r=read();
    for(int i=0;(1LL<<i)<=n;i++){
        if ((n>>i)&1){
            int LL=1LL<<i;
            int RR=(1LL<<(i+1))-1;
            if (LL>r){
                continue;
            }
            if (RR<l){
                continue;
            }
            ans+=min(r, RR)-max(l,LL)+1;
        }
    }
    printf("%lld\n", ans);
}