USACO--3.1Humble Numbers

这个题的难点在于如何顺序的产生Humble Numbers。考虑我们已经得到前k个Humble Numbers，如果得到第k+1个Humble Numbers？对每个素数,在前k个Humble Numbers中选择一个数与其相乘的结果恰好大于第k个Humble Numbers，然后我们的第k+1个数就是这些结果中的最小值。当然如果对每个素数每次都要遍历一遍前k个Humble Numbers，肯定会超时，但是我们注意到其实我们只要从上一次遍历的地方开始进行本次的遍历就行了，所以可以用一个数组记录每个素数遍历的起始位置。

代码如下：

/*
ID:15674811
LANG:C++
PROG:humble
*/

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define INF 0x7fffffff  ///INF不要定义的太小
int ans[110000];
int cnt[110];

int main()
{
    freopen("humble.in","r",stdin);
    freopen("humble.out","w",stdout);
    ///freopen("lkl.txt","r",stdin);
    int n,m,a[110];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
         for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
         ans[1]=1;
         for(int i=0;i<n;i++)
            cnt[i]=1;
         for(int i=2;i<=m+1;i++)
         {
             int Min=INF;
             for(int j=0;j<n;j++)
             {
                 while(a[j]*ans[cnt[j]]<=ans[i-1])
                     cnt[j]++;
                 if(a[j]*ans[cnt[j]]>ans[i-1]&&a[j]*ans[cnt[j]]<Min)
                     Min=a[j]*ans[cnt[j]];
             }
             ans[i]=Min;
         }
         printf("%d\n",ans[m+1]);
    }
  return 0;
}