Найти количество цифр, не делимых на X в сотом ряду треугольника Паскаля

Question

Мне нужно выяснить количество цифр, которые не делятся на число x в сотой строке треугольника Паскаля.

Алгоритм, который я применил, чтобы найти его: так как треугольник Паскаля является степенямииз 11, начиная со второй строки, n-ую строку можно найти с помощью 11 ^ (n-1), и ее легко можно проверить, для которой цифры не делятся на x.

Как это выяснить для большихчисла, когда n равно 99 или 100?Есть ли другой алгоритм, который можно применить, чтобы найти это?

Answer 1

Вы можете напрямую рассчитать значения треугольника Паскаля, используя факториалы (n! / (N-k + 1)! (K-1)! N-ая строка, k-е значение). Вы можете начать с k = 1, постепенно вычислять биномиальный коэффициент, и в n / 2 шагах вы можете найти число, не делимое на x.

выбирать (n, k + 1) = выбирать (n, k) * (n-k + 1) / k, где выбирать (n, k) = (n! / (N-k + 1)! (K -1)!

Answer 2

Вам не нужны точные значения сотой линии треугольника. Это нормально, чтобы рассчитать value mod x. Просто постройте треугольник как обычно, но применяйте операцию модуля везде - вам не понадобятся большие числа.