150
poj 2545 Hamming Problem
参考别人的思路写的，别人的这种算法很给力！
效率很高O（n）的效率
#include <iostream>
#include <stdio.h>
using namespace std;
__int64 ans[1000000];
__int64 getMin(__int64 a,__int64 b,__int64 c)
{
__int64 rs=0;
rs=a<b?a:b;
rs=rs<c?rs:c;
return rs;
}
int main()
{
__int64 a,b,c,M;
scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&M);
__int64 a2,a3,a5,i,tmp,n;
a2=a3=a5=0;
ans[0]=1;
for(i=1;i<=M;i++)
{
tmp=getMin(ans[a2]*a,ans[a3]*b,ans[a5]*c);
ans[i]=tmp;
if(tmp==ans[a2]*a)
++a2;
if(tmp==ans[a3]*b)
++a3;
if(tmp==ans[a5]*c)
++a5;
}
printf("%I64d\n",ans[M]);
return 0;
}
最后更新：2017-04-03 14:53:55