这篇博客是从旧博客 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;
}