题目分析

题意简述

给定三个整数 $p$, $q$, $r$，找到一个进制 $B$（$2 \leq B \leq 16$），使得在 $B$ 进制下 $p \times q = r$。如果有多个满足条件的 $B$，输出最小的；如果没有，输出 $0$。

输入

• 多组测试用例，每组给出 $p$, $q$, $r$。
• 所有数字均为数字字符（$0$-$9$），范围 $1 \leq p, q, r \leq 1,000,000$。

输出

每组测试用例的结果，表示满足条件的最小进制 $B$ 或 $0$。

解题思路

进制转换

将 $p$, $q$, $r$ 从 $B$ 进制转换为十进制后验证 $p \times q = r$。
注意： 数字的每一位必须小于 $B$，否则 $B$ 进制下该数字非法。

枚举优化

1. $B$ 的最小可能值：$max\\_digit + 1$（$max\\_digit$ 是 $p$, $q$, $r$ 中最大的数字）。
2. $B$ 的最大值：$16$，直接枚举 $B$ 从 $max\\_digit + 1$ 到 $16$。
3. 提前终止：一旦找到满足条件的 $B$，立即返回，保证结果是最小的。

代码实现

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		vector<int> digitA, digitB, digitC;
		int mxDigit = 0;
		while(a > 0){
			int A = a%10;
			digitA.push_back(A);
			if(A > mxDigit) mxDigit = A;
			a/=10;
		}
		while(b > 0){
			int B = b%10;
			digitB.push_back(B);
			if(B > mxDigit) mxDigit = B;
			b/=10;
		}
		while(c > 0){
			int C = c%10;
			digitC.push_back(C);
			if(C > mxDigit) mxDigit = C;
			c/=10;
		}
		int wsA = digitA.size(), wsB = digitB.size(), wsC = digitC.size();
		bool get = 0;
		for(int BB = mxDigit+1; BB <= 16; BB++){
			long long int aa = 0, bb = 0, cc = 0;
			for(int j = wsA-1; j >= 0; j--){
				aa*=BB;
				aa+=digitA[j];
			}
			for(int j = wsB-1; j >= 0; j--){
				bb*=BB;
				bb+=digitB[j];
			}
			for(int j = wsC-1; j >= 0; j--){
				cc*=BB;
				cc+=digitC[j];
			}
			if(aa*bb==cc){
				get = 1;
				printf("%d\n", BB);
				break;
			}
		}
		if(!get){
			printf("0\n");
		}
	}
	return 0;
}

代码说明

1. 输入处理
   • 使用 string 读取 $p$, $q$, $r$，避免数值过大或前导零问题。
2. 进制转换
   • to_decimal 函数将字符串从 $B$ 进制转换为十进制，并检查每一位是否合法。
3. 枚举优化
   • $max\\_digit + 1$ 是 $B$ 的最小可能值，直接枚举到 $16$。
4. 提前终止
   • 找到第一个满足条件的 $B$ 后立即退出循环，保证结果最小。