尴尬的数字（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

14

解题思路

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

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

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

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

那么将abs(正确数 - 三进制错误数)写成$i\ast 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\ast 3^j$那么对于暴力枚举这个N同样也是正确的

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