题解：2024牛客暑期多校第2场——E [GCD VS XOR]

英文题干

Ben has a positive integer . He wants you to find another positive integer , which is strictly less than , so that the equation holds. Can you help him?

where ⊕ is bitwise XOR operation.

Input:

The first line contains a single integer — the number of test cases. The only line of each test case contains a single integer .

Output:

For each testcase, output a single positive integer , if you find a feasible answer, or −1 otherwise.

中文题干

Ben有一个正整数。他希望你找到另一个严格小于的正整数，使得方程成立。你能帮助他吗？

其中⊕表示按位异或操作。

思路

1. 首先，若x为奇数：

   先介绍【⊕配对性定理】：若a为任意非负偶数，则必有 a⊕1=(a+1) 。利用这个定理，又由⊕的可交换性和大于2且相邻的两个数必互质，故当x为奇数时，x-1即为答案。

2. 其次，若x为偶数。

   [1].若x是2的整数幂, y不存在。

   [2].否则，只需要寻找x最多能被2的多少次方整除(可以利用 x&-x 求得)，用x减去这个数即可。

3. 最后，注意x=1需要特判一下。

(P.S:本题可以通过找规律直接获得结论，严谨证明见这篇文章）

AC代码

时间复杂度：O()

#include <iostream>
#define ll long long
using namespace std;
ll k, n;

void solve() {
    cin >> n;
    if (n == 1)
    {
        cout << -1 << endl;
        return;
    }

    if (n % 2 == 1)
    {
        cout << n - 1 << endl;
        return;
    }
    ll d = n & -n;
    if (d == n)
    {
        cout << -1 << endl;
    }
    else {
        cout << n - d << endl;
    }
}

signed main()
{
    cin >> k;
    while (k--) {
        solve();
    }

    return 0;
}
// Inspired by LXY & ZRJ