题解 B2141 【确定进制】

囧仙 · 2021-07-03 10:53:40 · 题解

题目大意

给定 p,q,r ，确定一个进制使得 p\times q=r 。

题解

题目中有一个条件： p,q,r 上的字符都是整数。因此，我们大可不必考虑烦人的字母（比如十六进制下有 \verb!ABCDEF! 这几个字母）。当我们直接读入 p,q,r 后，它就是以十进制的形式被读入的。我们提取它的每一位，也是要以十进制的方式提取（即每次除以 10 ，余数即为当前的最后一位）。

考虑一个进制 B 合法的条件。首先它应该大于 p,q,r 中出现的所有数字，然后我们要做的就是将 p,q,r 在字面上以 B 进制的形式转化。（可能听起来有点晦涩，其实意识是把读入的东西（相当于字符串）转化为 B 进制）。

以 p 举例：我们枚举它的每一位，其中第 i 位乘上 B^i ，再求和，就可以计算出他被转化为 B 进制的样子了。

如法炮制，分别将 p,q,r 转化成 a,b,c ，然后判断是否 a\times b=c 就能判断 B 是否合法。我们从小到大枚举每个 B 即可。

要注意的是，虽然题目上写出了 p,q,r\le 10^6 ，但是将其转化为 B 进制后可能相乘超过 \text{int} 。例如，当 p=q 的字面量为 1000000 时，转化为 16 进制后值就变成了 16,777,216 ，再相乘会超过 \text{int} 的最大值 2^{31}-1 。因此，该题中我们需要使用 \text{long long}。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
i64 p,q,r,o,pp,qq,rr,s;
int main(){
    scanf("%d%d%d",&p,&q,&r);
    pp=p,qq=q,rr=r;
    while(pp) s=max(s,pp%10),pp/=10;
    while(qq) s=max(s,qq%10),qq/=10;
    while(rr) s=max(s,rr%10),rr/=10;
    up(s+1,16,t){
        pp=p;i64 a=0; o=1; while(pp) a+=o*(pp%10),o*=t,pp/=10;
        qq=q;i64 b=0; o=1; while(qq) b+=o*(qq%10),o*=t,qq/=10;
        rr=r;i64 c=0; o=1; while(rr) c+=o*(rr%10),o*=t,rr/=10;
        if(a*b==c) printf("%d\n",t),exit(0);
    }
    puts("0");
    return 0;
}