确定进制

题目

小f穿过须弥的沙漠，来到了水之国枫丹，一个宣扬正义的国度。不同于其他国家，在小f正在思考如何觐见水神时，水神芙卡洛斯竟然亲自来见了小f。

但是芙卡洛斯是一位有趣中二的神明，她希望与小f进行智力方面的决斗。具体来说，她会给小f三个数a,b,c，表示a×b=c，需要小f回答她在什么进制下这个等式成立。

小f这次完美解决了问题，但是派蒙却晕了。她找到了你，希望你告诉她问题的答案是什么。

输入：三个数 a, b, c。
输出：一个数 x，表示等式在 x 进制下成立。如果等式在多个进制下成立，输出最小的那个进制。如果没有合适的进制，输出 0。
数据范围：a, b, c 每位都是数字，且 1 ≤ a, b, c ≤ 100000，x ∈ [2, 16]。

样例：

6 9 42

13

思路

枚举进制 x 从 2 到 16，对每个 x 做两件事：① 用 isValid 检查 a、b、c 的每一位数字是否都 < x（x 进制里不允许出现 ≥ x 的数字）；② 用 toDecimal 将三个数从 x 进制转为十进制，验证 a × b == c 是否成立。找到第一个满足条件的 x 输出，若无则输出 0。

toDecimal 的做法：用 % 10 从低位到高位依次取出每一位数字，乘以对应的 x 的幂次（power 从 1 开始，每轮 ×x），累加即得十进制值。

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

bool isValid(int n, int x){
    while(n!=0){
        if(n%10>=x){
            return false;
        }
        n/=10;
    }
    return true;
}

int toDecimal(int n, int x){
    int gewei=0,decimal=0,power=1;
    while(n!=0){
        gewei=n%10;
        decimal+=gewei*power;
        n/=10;
        power*=x;
    }
    return decimal;
}

bool check(int a, int b, int c, int x){
    if(!isValid(a,x)||!isValid(b,x)||!isValid(c,x)){
        return false;
    }
    if(toDecimal(a,x)*toDecimal(b,x)==toDecimal(c,x)){
        return true;
    }
    return false;
}

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    for(int x=2;x<=16;x++){
        if(check(a,b,c,x)){
            cout<<x<<endl;
            return 0;
        }
    }
    cout<<0<<endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(15 × log₁₀ N)，枚举 15 个进制，每次各函数循环次数为数的十进制位数。
• 空间复杂度：O(1)，只用常数个变量。

← 返回菜鸟的coding