#include <iostream> #include <queue> #include <string> using namespace std; typedef unsigned int uint; //====================================================================== const uint maxn = 10000; //====================================================================== class State; static State* _source = NULL; static State* _target = NULL; static char* _toDigit = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; class State { State* _parent; uint _level; uint _digit; public: void set(State* parent, uint level, uint digit) { _parent = parent; _level = level; _digit = digit; } void unset() { set(0, 0, 0); } bool isSet() { return _parent != 0; } State* getParent() const { return _parent; } uint getLevel() const { return _level; } string getDigit() const { return string("") + _toDigit[_digit]; } uint getSum() const { return (this - _source) / maxn; } uint getResidue() const { return (this - _source) % maxn; } friend ostream& operator<<(ostream& strm, const State& state); }; //====================================================================== ostream& operator<<(ostream& strm, const State& state) { return strm << "(" << state.getSum() << "," << state.getResidue() << "," << state.getLevel() << ")"; } //====================================================================== static State _table[maxn+1][maxn]; //====================================================================== // Return string for smallest multiple of n with digit sum n string f(uint n, uint base = 10) { // Bounds checking if (n > maxn || base < 2 || base > 36) return "Unknown"; // Return solution for n = 0 if (n <= 0) return "0"; // Set source and target states _source = &_table[0][0]; _target = &_table[n][0]; // Clear all states for (uint s = 0; s <= n; s++) for (uint r = 0; r < n; r++) _table[s][r].unset(); // Set source state _source->set(_source, 0, 0); // Add source state to queue queue<State*> stateQueue; stateQueue.push(_source); // Loop through queue for (;;) { // If queue empty, we failed if (stateQueue.empty()) return "None"; // Pop parent State* parent = stateQueue.front(); stateQueue.pop(); // For each digit for ( uint digit = 0, level = parent->getLevel()+1, sum = parent->getSum(), residue = (base*parent->getResidue())%n; digit < base && sum <= n; digit++, sum++, residue = (residue+1)%n ) { // Find child state State* child = &_table[sum][residue]; // If child already set, skip it if (child->isSet()) continue; // Set the child child->set(parent, level, digit); // If target is set, go create number if (_target->isSet()) goto buildAnswer; // Add child to queue stateQueue.push(child); } } // Build answer buildAnswer: string answer = ""; for (State* s = _target; s != _source; s = s->getParent()) answer = s->getDigit() + answer; // Return answer return answer; } // Generate b-file for A002998 int main() { for (uint n = 0; n <= maxn; n++) cout << n << " " << f(n) << endl; return 0; }