题解：CF2074C XOR and Triangle

XZDZD · 2025-03-12 13:40:44 · 题解

CF2074C XOR and Triangle

二分做法

根据异或的规律我们不难发现，一个数异或它的一半的结果大于这个数本身，异或它的四分之一的结果会比刚才的小。

具体的证明本蒻给不出（悲）。

AC Code

#include<bits/stdc++.h>
#define ll long long
const int N = 1e5 + 10;
using namespace std;
ll n;
int main(){
    ios::sync_with_stdio(0);
    int T;
    cin>>T;
    while (T--) {
        cin>>n;
        if (n == 2){
            cout<<"-1"<<'\n';continue;
        } 
        ll l = 1,r = n;
        bool ok = true;
        while (l < r) {
            ll mid = (l+r)>>1;
            ll p = mid ^ n;
            if(p+mid > n && p+n > mid && mid+n > p) {
                cout<<mid<<endl;ok=false;ok1=false;break;
            }else {
                l = mid + 1; //单方向二分就可以了，这里是向上，下面有向下的。 
            }
        }
    /*  第二种二分办法 
        if(ok1){
            while (l < r) {
            ll mid = (l+r)>>1;
            ll p = mid ^ n2;
            if(p+mid > n && p+n > mid && mid+n > p) {
                cout<<mid<<endl;ok=false;break;
            }else {
                r = mid;
            }
        }
        }
    */  
        if(ok) cout<<"-1"<<'\n';
    }
    return 0;
}