Число, делящееся на n и с суммой цифр n

#include <iostream>
#include <vector>
#include <string>
#include <ctime>
#include <cassert>
 
int N, minRow, maxRow;
const int maxN = 1000;
const int maxNum = (maxN / 9) + 4;
 
struct Cell {
    Cell( void ) : len(0) {}
    std::string Print( void ) const;
    
// data 
    short digit;
    short len;
    short sum;
    short rem;
    const Cell * parent;
};
 
std::vector <std::vector <Cell> > tbl;
std::vector <int> rowFill;      
 
std::string Cell::Print( void ) const
{
    std::string result;
    assert(len);
    const Cell * cell = this;
    while (cell) {
        result += '0' + cell->digit;
        const Cell * nxt = cell->parent; 
        if (!nxt) break;
        for (int i = nxt->len; i < cell->len - 1; ++i)
            result += '0';
        cell = nxt; 
    }
    return result;
}
 
Cell * Check( int digit, int rem, int len, const Cell & parent )
{
    int row = digit + parent.sum;
    if (row > N) return 0;  // sum exceeds limit
    
    rem = (rem + parent.rem) % N;
    Cell & dst = tbl[row][rem];
    if (dst.len) return 0;
    
    dst.digit = digit;
    dst.len = len;
    dst.sum = row;
    dst.rem = rem;
    dst.parent = &parent;
    
    if (rem == 0 && row == N) 
        return &dst;
 
// adjust maxRow
    if (row < N && row > maxRow)
        maxRow = row;
        
// adjust minRow
    if (++rowFill[row] >= N) {
//      printf("row %d is full\n", row);
        if (row == minRow)
            for (; minRow < N; ++minRow)
                if (rowFill[row] < N) break;
    }           
        
    return 0;
}
 
Cell * DoCalc( void )
{
// alloc row fill counts
    rowFill.clear();
    rowFill.resize(N + 1);
    
// alloc table
    tbl.resize(N + 1);
    for (size_t i = 0; i < tbl.size(); ++i) {
        tbl[i].clear();     // cleanup prev data
        tbl[i].resize(N);
    }
 
// add first 10 cells
    for (int i = 0; i < 10; ++i) {
        Cell & dst = tbl[i][i % N];
        dst.digit = dst.sum = i;
        dst.len = 1;
        dst.rem = i % N;
        dst.parent = 0;
        if (i == N) return &dst;
        ++rowFill[i];
    }
    
// main loop    
    minRow = maxRow = 1;
    int prvRem = 10 % N;
    for (int num = 1; num < maxNum; ++num) {
        int endRow = maxRow;
        for (int digit = 1; digit < 10; ++digit) {
            int rem = (prvRem * (digit % N)) % N;
            int begRow = minRow - 9;
            if (begRow < 0) begRow = 0;
            int endRow = maxRow;
            for (int row = begRow; row <= endRow; ++row) {
 
                // skip the row if it's full
                if (rowFill[digit + row] >= N) continue;
                
                for (int col = 0; col < N; ++col) {
                    Cell & parent = tbl[row][col];
                    if (!parent.len) continue;
                    if (parent.len > num) continue;
                    Cell * cell = Check(digit, rem, num + 1, parent);
                    if (cell) return cell;
                }
            }       
        }   
        prvRem = (prvRem * 10) % N;  // adjust remainder
    }
    
    return 0;
}
 
int main( void )
{
    time_t begT, endT;
    time(&begT);
 
    for (N = 1; N <= maxN; ++N) {
        Cell * cell = DoCalc();
        printf("[%d] %s\n", N, cell ? cell->Print().c_str() : "not found"); 
 
#if PRINT_FILL      
        size_t tbl_size = (N + 1) * N;
        printf("size = %d (%d), %d%%\n", vec.size(), tbl_size, vec.size() * 100 / tbl_size);
#endif      
    }   
 
    time(&endT);
    int second = difftime(endT, begT);
    printf("calc time = %d:%02d\n", second / 60, second % 60);
    
    return 0;
}