Project Euler 043

First, try with all multiples of 17 that has different digits:

$$\begin{aligned} \overline{cba} \equiv \mod 17 \end{aligned}$$

Since $a$, $b$ and $c$ are known values, the next step is:

$$\begin{aligned} \overline{dcb} \equiv \mod 13 \end{aligned}$$

to calculate the value of $d$:

$$\begin{aligned} 100d + 10c + b &\equiv 0 \mod 13\cr d &\equiv -(10c+b)\text{inv}(100,13) \mod 13 \end{aligned}$$

More generally:

$$\begin{aligned} 100z + 10y + x &\equiv 0 \mod p\cr z &\equiv -(10y+x)\text{inv}(100, p) \mod p \end{aligned}$$

Since $x$ and $y$ are known values, $-(10y+x)\%p$ is also known. To calculate $\text{inv}(100, p)$ is enough with a preprocessing for every prime number from $2$ to $17$. Finally, the equation is similar to: $z \equiv k \mod p$, so for every digit the search space is reduced for just $1$ or $2$ values.

Time Complexity: $O(20\times 10\times 10)$

Just for $2$ and $5$ is needed to iterate from $0$ to $9$ and there are just $20$ numbers that met the requirements for $17$.