HDOJ 3199 Hamming Problem

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


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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Author: Tanky Woo
// HDOJ 3199
#include <iostream>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注