1331:Multiply

keyword

n進表記　C++

概要

数字を表す文字列がa,b, cが与えられたときa*b==cが成り立つのは基数(10^6以下)をいくつにすればよいか求める問題。
基数変換はO(log n)でできるので愚直に実装すれば間に合う。基数の下限には注意しておくこと。

inline ll changeBase(ll a, int base){
    ll ret = 0;
    ll d = 1, bb = 1;
    while(a/d){
        ret += ((a/d)%10)*bb;
        d *= 10;
        bb *= base;
    }
    return ret;
}

int main(){
    ll p, q, r, d;
    int rept, base, st;
    scanf("%d",&rept);

    LOOP(rept){
        scanf("%lld%lld%lld",&p,&q,&r);
        st = 1;
        d = 1;
        while(p/d){
            st = max(st,(int)((p/d)%10));
            d *= 10;
        }
        d = 1;
        while(q/d){
            st = max(st,(int)((q/d)%10));
            d *= 10;
        }
        d = 1;
        while(r/d){
            st = max(st,(int)((r/d)%10));
            d *= 10;
        }
        for(base=st+1;base<=16;base++)if(changeBase(p,base)*changeBase(q,base)==changeBase(r,base))break;
        if(base>16) base=0;
        printf("%d\n",base);
    }

    return 0;
}