Введём обозначение $$$A = 10$$$

Решение за $$$O(n A^3)$$$: заведём динамику $$$dp[n][d][g]$$$ — количество чисел длины $$$n$$$ таких, что последняя цифра равна $$$d$$$ и её НОД с предыдущей цифрой равен $$$g$$$. База динамики – переберём всевозможные двузначные числа, состояние определяется второй цифрой и её НОДом с первой, увеличиваем значение в состоянии на $$$1$$$. Считать эту динамику можно вперёд: $$$dp[n + 1][e][\gcd(d, e)] += dp[n][d][g], g \neq \gcd(d, e)$$$. Ответ — сумма по всем состояниям динамики.

Решение за $$$O(n A^2 \log A)$$$: заметим, что число состояний динамики на самом деле не $$$A^2$$$, а $$$A \log A$$$, поскольку $$$g | d$$$, состояний со вторым параметром равным $$$g$$$ будет $$$\frac{A}{g}$$$. Сумма $$$\sum \limits_{g=1}^{A} \frac{A}{g}$$$ оценивается как $$$A \log A$$$, на практике выходит $$$33$$$ состояния.

Эта динамика оптимизируется бинарным возведением матрицу в степень: возьмём матрицу $$$M$$$ размерами $$$33\ \times 33$$$, Пронумеруем как угодно все состояния, затем определим $$$M_{i,j} = $$$ можно ли из состояния $$$i$$$ перейти в состояние $$$j$$$, дописав одну цифру. Затем возводим $$$M$$$ в степень $$$n-2$$$ и домножаем на базу. Получаем время работы $$$O(t (A \log A)^3 \log n)$$$.

Заметим, что в бинарном возведении в степень мы каждый раз считаем $$$M^{2^k}$$$, но это можно сделать один раз. А с предподсчитанными степенями матрицы $$$M$$$ мы можем домножать на них не матрицу $$$33 \times 33$$$, а одномерный вектор размера $$$33$$$. Тогда время работы составит $$$O((A \log A)^3 \log n + t (A \log A)^2 \log n)$$$.