HDU 5175 Misaki's Kiss Again：異或與 GCD 的數學轉化

題目大意

給定 N (0 < N ≤ 10¹⁰)，找出所有 M (1 ≤ M ≤ N) 使得 gcd(N, M) = N XOR M。多組測試，輸出滿足條件的 M 個數及升序列表。

解題分析

設 K = N XOR M，則 M = N XOR K。原式變為：

gcd(N, N XOR K) = N XOR (N XOR K) = K

即 gcd(N, M) = K，說明 K 必須是 N 的約數。因此只需枚舉 N 的所有約數 K，計算 M = N XOR K，驗證：

1. gcd(N, M) == K
2. M != 0 且 M ≤ N
3. M != N（因 gcd(N,N)=N ≠ N XOR N=0）

約數個數最多約 10⁵，枚舉可行。注意 N ≤ 10¹⁰ 需用 64 位整數。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

int main() {
    ll n; int ca = 1;
    while (cin >> n) {
        vector<ll> fac, ans;
        for (ll i = 1; i * i <= n; ++i)
            if (n % i == 0) {
                fac.push_back(i);
                if (i * i != n) fac.push_back(n / i);
            }
        for (ll k : fac) {
            ll m = n ^ k;
            if (m == 0 || m > n) continue;
            if (gcd(n, m) == k) ans.push_back(m);
        }
        sort(ans.begin(), ans.end());
        printf("Case #%d:\n%zu\n", ca++, ans.size());
        for (size_t i = 0; i < ans.size(); ++i) {
            if (i) printf(" ");
            printf("%lld", ans[i]);
        }
        puts("");
    }
    return 0;
}