[SC2B Key Contest]Math challenge

ok, the key is yours:

xxxxxx-xxxx-xxxxxx-xxxx-xxxxxx

have fun

-----------------------------------------
Original Message:
Sure thing
9090754242258600
1710153888867000

-----------------------------------------
Original Message:
could you give me 2 examples for x for which ds(x) = ds(x * 137)?

-----------------------------------------
Original Message:
Answer =
20444710234716473

Solution is a dynamic programming algorithm. State is based on the last k digits of the number, lazily computing the digit sum of 137*x digit by digit, storing the next 4 digits to the left of the last k digits (using the fact that 9*137 + 99 < 10000). I iterate through the values of k from 0 to 17, increasing it by one each time (so that at the end we have the values for 18), computing the number of numbers x for which the next 4 digits to the left are "a" and the difference between ds(x) and ds(137*x) (up to the last k digits) is "b".

Code below:

#include<cstdio>
#include<cstdlib>

using namespace std;

int main() {
        long long **now, **next;
        now = new long long*[10000];
        next = new long long*[10000];
        for(int i = 0; i<10000; i++) {
                now[i] = new long long[401];
                next[i] = new long long[401];
                now[i] += 200;
                next[i] += 200;
                for(int j = -200; j<=200; j++) {
                        now[i][j] = next[i][j] = 0;
                }
        }
        now[0][0] = 1;
        for(int i = 0; i<18; i++) {
                for(int j = 0; j<10000; j++) {
                        for(int k = -200; k<=200; k++) {
                                next[j][k] = 0;
                        }
                }
                for(int a = 0; a<10000; a++) {
                        for(int b = -162; b<=162; b++) {
                                for(int d = 0; d<=9; d++) {
                                        int na = a/10 + 137*d, nb = b - a%10 + d;
                                        next[na][nb] += now[a][b];
                                }
                        }
                }
                long long **t = now;
                now = next;
                next = t;
        }
        long long ans = 0;
        for(int i = 0; i<10000; i++) {
                for(int j = -200; j<=200; j++) {
                        int a = i, b = j;
                        while(a != 0) {
                                b -= a%10;
                                a/=10;
                        }
                        if(b == 0) {
                                ans += now[i][j];
                        }
                }
        }
        printf("%lld\n",ans);
}