c# - 在帕斯卡三角形的第 100 行中找到不能被 X 整除的位数

Question

我需要找出帕斯卡三角形第 100 行中不能被数字 x 整除的位数。

我为了找到它而应用的算法是：由于帕斯卡三角形从第二行开始是 11 的幂，所以第 n 行可以通过 11^(n-1) 找到，并且可以很容易地检查哪些数字不能被整除X。

当 n 等于 99 或 100 时，如何找出大数？有没有其他算法可以用来找到这个？

Answer 1

您可以使用阶乘 (n!/(n-k+1)!(k-1)!nth row, kth value) 直接计算帕斯卡三角形的值。您可以从 k=1 开始，逐步计算二项式系数，并在 n/2 步中找到不能被 x 整除的数字。

选择(n,k+1) = 选择(n,k)*(n-k+1)/k 其中选择(n,k) = (n!/(n-k+1)!(k-1) ！

Answer 2

您不需要三角形第 100 行的精确值。计算就OK了value mod x。像往常一样构建三角形，但在任何地方都应用模数运算 - 你不需要大数字。