USACO 3.1 Humble Numbers

The idea is to generate and maintain a sorted list of humble numbers:

  • Each humble number can be generated together with this sorted list, and with one of the seed prime numbers.
  • For each humble number, there is one and only one way of generating the number - in other words the prime factors are fixed for a given humble number.
  • For each prime factor number, maintain an index into the humble number sorted list. The indexed number in the humble number list would be the next number that this prime factor should multiply.
  • The invariant is, at each iteration, the smallest possible humble number is generated, and each index associated with each prime factor is incremented by one, if the prime factor contributes to the generation (num % prime == 0).

Following this idea, the humble numbers can be generated systematically without duplicates, and we only need maintain a single sorted list of humble numbers.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <utility>
#include <cmath>
#include <string>
#include <unordered_map>
#include <climits>
#include <sstream>

using namespace std;

int N, K;

int main() {
ifstream fin("humble.in");
ofstream fout("humble.out");

fin >> K >> N;
vector<int> dp(N + 1, INT_MAX);
vector<int> num(K, 0);
vector<int> indices(K, 0);
for (int i = 0; i < K; ++i) {
fin >> num[i];
}
dp[0] = 1;
for (int i = 1; i <= N; ++i) {
for (int j = 0; j < K; ++j) {
dp[i] = std::min(dp[i], dp[indices[j]] * num[j]);
}
for (int j = 0; j < K; ++j) {
if (dp[i] % num[j] == 0) {
++indices[j];
}
}
}
fout << dp[N] << endl;
cout << dp[N] << endl;
}