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;
}