Yen-Jen loves cat very much.
Now, there are 10^{18}1018 cats standing in a line, the i^{th}ith cat's cost value c_ic**i is equal to ii, the i^{th}ith cat's index is also equal to ii.
Now, Yen-Jen wants to buy some cats with continuous index, but he only has SS dollars. He wants to buy some cats with continuous indices. In order to buy cat with index x, x + 1, cdots, y - 1, yx,x+1,⋯,y−1,y, he needs to spend x oplus (x + 1) oplus cdots oplus (y - 1) oplus yx⊕(x+1)⊕⋯⊕(y−1)⊕y dollars. oplus⊕ is the bitwise exclusive-or operator.
Now, he wants to ask you TT questions. In each question, he has SS dollars, and he wants the indices of cats in range [L, R][L,R]. What's the maximum number of cat that Yen-Jen can buy? If he can't buy any cat, please report -1 instead.
Input
The first line of the input file contains one integer TT denotes the number of questions that Yen-Jen wants to challenge you.
Then, in the next TT lines, each line contains one question. In each line, there are three integers L, R, SL,R,S, which means that Yen-Jen has SS dollars, and he wants to buy cats whose indices are in the range [L, R][L,R].
- 1 le T le 5 imes 10^51≤T≤5×105
- 1 le L le R le 10^{18}1≤L≤R≤1018
- 0 le S le 2 imes 10^{18}0≤S≤2×1018
Output
In each question, output the maximum number of cats that Yen-Jen can buy. If Yen-Jen can't buy any cats, output -1 instead.
样例输入复制
2
1 1 0
2 2 2
样例输出复制
-1
1
由于连续四个偶数奇数异或起来为0，因此只需要暴力([l, l+3])以及([r-3, r])这两部分然后对答案求最大值即可。以及l到r的异或和其实可以(O(1))计算。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
long long getXor(long long start, long long x) {//获得从start开始到x的异或和
if(!(start & 1)) {
if(x & 1) {
if(((x - 1) / 2) & 1) return 0;
else return 1;
} else {
if(!((x / 2) & 1)) return x + 1;
else return x;
}
} else {//start为偶数有规律 为奇数的话相当于为偶数的情况再异或以下start
if(x & 1) {
if(((x - 1) / 2) & 1) return 0 ^ start;
else return 1 ^ start;
} else {
if((x / 2) & 1) return (x + 1) ^ start;
else return x ^ start;
}
}
}
int solve(int l,int r)
{
int res=0;
if(r-l+1<=10){
for(int i=l;i<=r;i++) res^=i;
return res;
}
else {
while(l%4!=0){
res^=l;
l++;
}
while(r%4!=3){
res^=r;
r--;
}
return res;
}
}
int main() {
int t;
cin >> t;
while(t--) {
ll l, r, s;
scanf("%lld%lld%lld", &l, &r, &s);
ll ans = 0;
ans = -1;
for(ll nx = l; nx <= l + 3; nx++) {
for(ll ny = r - 3; ny <= r; ny++) {
if(nx > ny) continue;
ll tmp = (getXor(1, ny) ^ getXor(1, nx - 1));
if(s >= tmp) ans = max(ans, ny - nx + 1);
}
}
if(ans != 0) printf("%lld
", ans);
else printf("%-1
", ans);
}
return 0;
}