2545:Hamming Problem

PKU

keyword

C++

概要

素数p1,p2,p3が与えられる。素因数がp1,p2,p3以外を含まないような数を小さい順に並べたときN番目の数を出力する問題。答えは10^18以下になる。
総数はそんなに多くならないので数列を全部作る。オーバーフローが起きるかどうかまずlogをとって判定する。この問題有名な問題らしいけど多分これは想定解ではないはず。何の工夫もしてないし。

int main(){
    ll a, b, c, n;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&n);
    double log1 = log(a), log2 = log(b), log3 = log(c), logub = 18*log(10)+EPS;
    ll i, j, k;
    vector<ll> ns;
    ll as[100], bs[100], cs[100];
    as[0] = bs[0] = cs[0] = 1;
    REP(i,80){
        as[i+1] = as[i]*a;
        bs[i+1] = bs[i]*b;
        cs[i+1] = cs[i]*c;
    }
    REP(i,80)REP(j,80)REP(k,80)if(i*log1 + j*log2 + k*log3 < logub){
        ns.PB(as[i]*bs[j]*cs[k]);
    }
    sort(ALL(ns));

    printf("%lld\n",ns[n]);
    return 0;
}