まだdebugしてないけど

for(i=0; i<K; i++) A[i] = K;
for(i=0; i<K; i++){
 for(f=1; f<10; f++){
  A[ (10^i * f)%K ]
   = min ( A[ (10^i * f)%K ], f );
 }
}
m = 0;
while(A[0]>m){
 i = 0;
 for(j=0; j<K; j++){
  if( A[j]>m && A[j]<A[i] ) i=j;
 }
 m=A[i];
 for(f = 1; f<10; f++){
  for(j=0; j<K; j++]{
   A[ ( i+10^j * f)%K ]
 = min(A[( i + 10^j * f )%K], A[ i ]+f );
  }
 }
}