尴尬的数字（C++，数学）

题目背景

Bessie 刚刚学会了不同进制数之间的转换，但是她总是犯错误，因为她的两个前蹄不能轻松的握住钢笔。

题目描述

每当 Bessie 将一个数转换成新的进制时，她总会写错一位数字。例如，她将 14 转化成 2 进制数，正确的结果是 1110，但她可能会写成 0110 或 1111。Bessie 从不会意外的增加或删减数字，所以她可能会写出以 0 开头的错误数字。

给出 Bessie 转换后 $N$ 的 2 进制形式和 3 进制形式，请计算出 $N$ 的正确数值（用十进制表示）。 $N$ 可能会达到 $10^9$ ，输入数据保证解的存在唯一性。

输入格式

第一行， $N$ 的 2 进制表示（有一位是错误的数字）。

第二行， $N$ 的 3 进制表示（有一位是错误的数字）。

输出格式

$N$ 的正确值。

样例 #1

样例输入 #1

1010
212

样例输出 #1

解题思路：

最容易想到的就是暴力枚举，将二进制的每一种可能错误与三进制的每一种可能错误比较，相同则为答案

这里不对这种方法进行说明，采用另一种方法

利用异或^的性质，枚举每一种二进制的可能错误

考虑到在三进制只错一位的前提下，如果得出的N是正确值

那么将abs(正确数 - 三进制错误数)写成 $i * 3^j$ 的形式，一定可以得到 $i < 3$

从而得出时间复杂度接近o(n)的算法

AC代码如下

#include <iostream>
#include <cmath>
using namespace std;

long long binTodec(string str) {//二进制转十进制
	int len = int(str.size());
	int power = 1;
	long long sum = 0;
	for (int i = len - 1; i >= 0; i--) {
		sum += power * (str[i] - '0');
		power *= 2;
	}
	return sum;
}

long long threeTodec(string str) {//三进制转十进制
	int len = int(str.size());
	int power = 1;
	long long sum = 0;
	for (int i = len - 1; i >= 0; i--) {
		sum += power * (str[i] - '0');
		power *= 3;
	}
	return sum;
}

int main() {
	string str_1, str_2;
	cin >> str_1 >> str_2;
	long long t_1 = binTodec(str_1);
	long long t_2 = threeTodec(str_2);
	int power = pow(2, int(str_1.size()) - 1);
	for (int i = 0; i < int(str_1.size()); i++, power /= 2) {//枚举二进制错误
		long long t_3, t_4;
		if ((str_1[i] - '0') ^ 1)//异或操作
			t_3 = abs((t_4 = t_1 + power) - t_2);
		else
			t_3 = abs((t_4 = t_1 - power) - t_2);
		while (t_3 % 3 == 0) t_3 /= 3;//检测是否正确
		if (t_3 < 3) {
			cout << t_4 << endl;
			break;
		}
	}
	return 0;
}

这里简单说明一下，为什么不可能有第二个N使得判定条件成立

~~众所周知~~，暴力枚举一定可以得出正确答案

如果有第二个N可以使得差值写成 $i * 3^j$ ，那么对于暴力枚举，这个N同样也是正确的

因为暴力枚举可以把三进制的 $j + 1$ 位修改，使得二进制修改后的值与之相等

秒客网