对于整数 n (1<=n<=10^8)。数到帕斯卡三角形中有多少个数字满足除以 7。 假设 s(n) 是输入为 n 的结果。
例如，我们有：s(1)=s(2)=s(3)=s(4)=s(5)=s(6)=0，s(7)=6。 因为当 n=7 时，我们有：1 7 21 35 35 21 7 1.有：7,21,35,35,21,7除以 7。
同样，当 n=8 时，我们有：1 8 28 56 70 56 28 8 1。所以s(8)=6+7=13. 等等...我需要计算 s(n) 与 n 是非常大的数字。
Ps：我知道这个问题与卢卡斯定理有关，但我不知道如何在这个问题中使用它。
从二项式系数表达式做功：
n! / (k! * (n-k)! )
这里你需要担心的只是表达式中有多少个 7 的因子。 在分子和每个分母项中计数 7s。 如果分子中有更多这样的术语，该条目是可整除的。 请注意，您只需用整数除法检查分母值即可执行此操作。
例如，当 n=7 时，扩展中有 8 个项([0,7] 中的 k)。 除了当 k=7 或 (n-k)=7 时，分母中未涵盖的 7 英寸n!。 因此，其他 6 项可被 7 整除。
当 n=8 时，两端有两个项(共 9 项)，涵盖所有 7。 因此，您有 5 个可分割的项。 在每一行中，您将在该行中多有一个条目，两端还有一个不可分割的条目：您将有 5，然后是 4，然后是 3，...可被 7 整除。 第 13 行将没有可被 7 整除的项。
然后看看第 14 行发生了什么：分子中有两个 7，但 15 个条目中的每一个分母中只有一个，除了k=7 时。 扩展此模式。
参数化留给学生作为练习。 请注意，当你到达 49 时，你有一个新的情况，因为这会在分子中引入两个7。 你的效果与从s=6到s=7时的效果相当。
这足以让你动起来吗？