P6861 [RC-03] 难题

$Result$

---

$Description$

给定一个数$n$，要求在$[1,n]$范围内选两个正整数，使得二者或和+异或和最大

数据范围：$n\le 10^{18}$

---

$Solution$

显然这两者的最大值必然都是$2^k-1$，$k$是$n$在二进制下的位数

时间复杂度：$O(logn)$

---

$Code$

#include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std;LL n,now=1; inline LL read() { char c;LL d=1,f=0; while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } signed main() { n=read(); while((now<<1)-1<n) now<<=1; now=(now<<1)-1; printf("%lld",now<<1); }