HDU7523 cats 的 k-xor

传送门

Solution

$k$ 进制下不进位加法的本质是，若两数第 $i$ 位相加后超过了 $k^i$，则减去 $k^i$。所以 $a+b \ge c$ 时问题有解，且当 $a+b>c$ 时，有 $k|(a+b-c)$。

1. 当 $a+b<c$ 时，$k$ 不存在。
2. 当 $a+b=c$ 时，取 $k>c$ 即可。$k$ 有无穷个。
3. 当 $a+b>c$ 时，枚举 $a+b-c$ 的因数 $k$，判断 $k$ 是否为所求。

时间复杂度 $O(T\sqrt{a} \log a)$

Code

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

ll T, a, b, c, ans;

bool check(ll k, ll a, ll b, ll c) {
    while (a || b || c) {
        if ((a % k + b % k) % k != c % k)
            return 0;
        a /= k; b /= k; c /= k;
    }
    return 1;
}

void solve()
{
    ans = 0;
    scanf("%lld%lld%lld", &a, &b, &c);
    if (a + b < c) {
        printf("0\n");
        return;
    } else if (a + b == c) {
        printf("-1\n");
        return;
    }
    for (int i = 2; i * i <= a + b - c; i++)
        if ((a + b - c) % i == 0)
            ans += check(i, a, b, c);
    ans += check(a + b - c, a, b, c);
    printf("%lld\n", ans);
}

int main()
{
    scanf("%lld", &T);
    while (T--) solve();
    return 0;
}