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

#include <cstdio>
#include <memory.h>
 
#define AUTHOR Qwertiy
 
#define MAXN 1024
#define MAXL 1024
 
signed char res[MAXL][MAXN][MAXN];
signed ms[MAXN];
 
void solve(unsigned n)
  {
  unsigned l, s, r, d, m;
  signed char *p;
 
  memset(res, -1, sizeof res);
  res[0][0][0] = 0;
 
  for(ms[l=0]=m=1; l<MAXL-1; ms[++l]=(m*=10)%=n)
    {
    for(s=0; s<=n; ++s)
      for(r=0; r<n; ++r)
        if(~res[l][s][r])
          for(d=0; d<10; ++d)
            if(s+d<=n && *(p=res[l+1][s+d]+(r+m*d)%n)>d)
              *p=d;
    
    if(~res[l][n][0])
      break;
    }
 
  printf("%4d: ", n);
 
  if(!~res[l][n][0])
    puts("Not found :(");
  else
    {
    while(!res[l][n][0])
      --l;
 
    for(s=n,r=0; l; s-=d,r=(n+(signed)(r-d*ms[--l])%(signed)n)%n)
      putchar('0'+(d=res[l][s][r]));
 
    putchar('\n');
    }
  }

#define Igor3D 0
#define Qwertiy 1
 
//#include "Igor3D.cpp"
#include "Qwertiy.cpp"
 
int main(void)
  {
  unsigned n;
 
  #if AUTHOR == Igor3D
    main_by_Igor3D();
  #elif AUTHOR == Qwertiy
    for(n=1; n<=1000; ++n)
      solve(n);
  #endif
 
  getchar();
  return 0;
  }

  for(ms[l=0]=m=1; l<MAXL-1; ms[++l]=(m*=10)%=n)
    {
    if(~res[l][n][0])
      break;
 
    for(s=0; s<=n; ++s)
      for(r=0; r<n; ++r)
        if(~res[l][s][r])
          for(d=0; d<10; ++d)
            if(s+d<=n && *(p=res[l+1][s+d]+(r+m*d)%n)>d)
              *p=d;
    }

  for(ms[l=0]=m=1; l<MAXL-1 && !~res[l][n][0]; ms[++l]=(m*=10)%=n)
    for(s=0; s<=n; ++s)
      for(r=0; r<n; ++r)
        if(~res[l][s][r])
          for(d=0; d<10; ++d)
            if(s+d<=n && *(p=res[l+1][s+d]+(r+m*d)%n)>d)
              *p=d;

for (int num = 0; num < num_digits; ++num)
 for (int digit = 0; digit < 10; ++digit) {
  val = pow(10, num);
  Check(val * i);
 }

struct Cell {
  short digit;   // сама цифра 
  short len;     // кол-во цифр в пути
  short sum;   // сумма цифр (key1)
  short rem;   // остаток (key2)
  short x, y;   // индекс предыдущей ячейки
};

if(s+d<=n && *(p=res[l+1][s+d]+(r+m*d)%n)>d)