atcoder:arc129（a,b,c）,abc228(a,b,c)题解

题解"/>

atcoder:arc129（a,b,c）,abc228(a,b,c)题解

arc129

A题：

题意：

输入N,L,R，求L~R这个区间内，有多少个数与N异或运算后小于N？（N^X<N）。

思路：

异或运算：在二进制下，0^0=1,1^1=0,0^1=1,1^0=1.

不难发现，当一个数的最高位1与同位置的1异或后，得到的数一定小于本身。所以只需要反复找N中的1位然后与该位置为1的数异或，结果一定小于本身。最后需要注意数在区间l-r即可。

代码如下：

#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<sstream>using namespace std;typedef long long ll;ll qpow(ll a,ll b)
{int ans=1;while(b>0){if(b&1){ans*=a;}a*=a;b>>=1;}return ans;
}int main(void)
{int t=1;ll n,l,r;//cin>>t;cin>>n>>l>>r;ll res=0;for(int i=62;~i;i--){if(n>>i&1){ll lls=max(l,1ll<<i);ll rrs=min(r,(1ll<<(i+1))-1);if(rrs>=lls)res+=rrs-lls+1;}}cout<<res<<endl;
}

B题：

题意：

有以下三个函数：

• If x<lx<l: dist(l,r,x)=l-xdist(l,r