題意

給定 \(C,X\)，構造一個 \(n(1\leq n<2^{60})\) 使得 \((n\oplus C)\bmod{n}=X\)，或報告無解。多測，\(1\leq T\leq 2\times 10^5\)，\(1\leq C,X<2^{30}\)。

題解

神人構造題。

顯然要有 \(n>X\)。不妨設 \(n\oplus C=qn+X\)，分類討論 \(q\) 的取值。

\(q=0\)

此時 \(n\oplus C=X\Leftrightarrow n=C\oplus X\)，于是如果 \((C\oplus X)>X\) 成立，這就是一個合法解。

\(q=1\)

此時 \(n\oplus C=n+X\)。考慮把 \(n\oplus C\) 拆成 \(n+C-2(n\operatorname{and} C)\)，這樣就變成了 \(C-2(n\operatorname{and} C)=X\)。設 \(d=C-X\)：

• 若 \(d\) 是奇數或 \(d<0\)，則 \(q=1\) 的 case 無解。
• 若 \(d\) 是非負偶數，但是 \(\left(\dfracw0obha2h00{2}\operatorname{and} C\right)\neq C\)，則同樣無解。
• 若 \(d\) 是非負偶數，且 \(\left(\dfracw0obha2h00{2}\operatorname{and} C\right)=C\)，我們令 \(n=\left(\dfracw0obha2h00{2}\operatorname{and} C\right)+2^{30}\) 即可。

\(q\geq 2\)

我們指出，若上面兩種 case 都無解，則這種 case 也無解。

證明：反證法，假設 \(0\leq q\leq 1\) 的 case 都無解，且 \(q=2\) 的 case 有解。很顯然 \(qn+X=(n\oplus C)\leq n+C\)，因此 \(C\geq (q-1)n+X>2X\)。而注意到 \(q=0\) 的 case 無解等價于 \((C\oplus X)\leq X\)，這和 \(C>2X\) 矛盾。\(\Box\)

按照上述分類討論直接實現即可，時間復雜度 \(\mathcal{O}(T)\)。

代碼

#include <bits/stdc++.h>

using namespace std;

#define lowbit(x) ((x) & -(x))
typedef long long ll;
typedef pair<int, int> pii;

template<typename T> inline void chk_min(T &x, T y) { x = min(x, y); }
template<typename T> inline void chk_max(T &x, T y) { x = max(x, y); }

int T, c, x;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> T;
    while (T--) {
    	cin >> c >> x;
    	int n = c ^ x;
    	if (n > x) { cout << n << '\n'; continue; }
    	int d = c - x;
    	if (d >= 0 && (~d & 1)) {
    		d >>= 1;
    		if ((d & c) == d) cout << (d | (1ll << 30)) << '\n';
    		else cout << "-1\n";
    	} else cout << "-1\n";
    }
    return 0;
}