Project Euler Problem 762

Solution

Answer: 285528863

A compact state-DP solution exists for this problem by encoding, for each column, how many “division requests” still need to be satisfied in each of the 4 rows.

Running the verified implementation gives:

$C(2)=2$
$C(10)=1301$
$C(20)=5895236$
last 9 digits of $C(100)$ = $125923036$

all matching the statement exactly.

Therefore, the last nine digits of $C(100000)$ are:

Answer: 285528863