Blog·Tanky WooABOUTRSS

HDOJ 3199 Hamming Problem

15 Aug 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=3199


HDOJ 1508 丑数那题基本上一模一样。 这题虽然看起来数很大,但是认真分析会发现,其实数很小的,因为输出也小于10^18。

// Author: Tanky Woo
// HDOJ 3199
#include 
using namespace std;

__int64 humble[100000];
__int64 _min(__int64 a, __int64 b, __int64 c)
{
    __int64 m;
    if(a < b)
        m = a;
    else
        m = b;
    if(m > c)
        m = c;
    return m;
}

int main()
{
    int e1=0, e2=0, e3=0;
    __int64 a1, a2, a3;
    int p1, p2, p3, n;
    while(scanf("%d %d %d %d", &p1;, &p2;, &p3;, &n;) != EOF)
    {
        e1 = e2 = e3 = 0;
        humble[0] = 1;
        for(int i=1; i<=n; ++i)
        {
            a1 = p1*humble[e1];
            a2 = p2*humble[e2];
            a3 = p3*humble[e3];
            humble[i] =  _min(a1, a2, a3);
            if(humble[i] == a1)
               e1++;
            if(humble[i] == a2)
               e2++;
            if(humble[i] == a3)
               e3++;
        }
        printf("%I64d\n", humble[n]);
    }
    return 0;
}