UVa1384/LA3700 Interesting Yang Hui Triangle

题目链接

  本题是2006年icpc亚洲区域赛上海赛区的题目

题意

  给出素数P和整数N，求杨辉三角第N+1行中不能整除P的数有几个，$P<1000,N\le 10^9$，结果要模10000后输出，并且四位数要输出前导0。

分析

  关于组合数取模，有一个很有趣的Lucas定理：
$$\left(\begin{array}{c}m\\ n\end{array}\right)\equiv \prod _{i=1}^k\left(\begin{array}{c}{m}_i\\ n_i\end{array}\right)\left(modp\right)$$
  其中$m_i$和$n_i$分别是m和n的p进制表示法中的各位数字，当m<n时，二项式系数 $\left(\begin{array}{c}m\\ n\end{array}\right)$规定为0。因此，若$\left(\begin{array}{c}m\\ n\end{array}\right)$是p的倍数，则至少存在一个$n_i>m_i$。反之，若$\left(\begin{array}{c}m\\ n\end{array}\right)$不是p的倍数，则所有$n_i\le m_i$必须都成立。
  由此可见，对输入N，求出其P进制表示法中的各位数字$N_i$，则杨辉三角第N+1行中不能整除P的数有$\prod \left(N_i+1\right)$个。

AC 代码

#include <iostream>
#include <iomanip>
using namespace std;int p, n, kase = 0;int solve() {int ans = 1;while (n) ans *= n%p + 1, n /= p;return ans % 10000;
}int main() {while (cin >> p >> n && (p || n))cout << "Case " << ++kase << ": " << setw(4) << setfill('0') << solve() << endl;return 0;
}