UVa1384/LA3700 Interesting Yang Hui Triangle
- 題目鏈接
- 題意
- 分析
- AC 代碼
題目鏈接
??本題是2006年icpc亞洲區域賽上海賽區的題目
題意
??給出素數P和整數N，求楊輝三角第N+1行中不能整除P的數有幾個， P < 1000 , N ≤ 10 9 P<1000,\;N≤10^9 P<1000,N≤109，結果要模10000后輸出，并且四位數要輸出前導0。
分析
??關于組合數取模，有一個很有趣的Lucas定理：
( m n ) ≡ ∏ i = 1 k ( m i n i ) ( m o d p ) \begin{pmatrix}m\\n\end{pmatrix}\equiv \prod_{i=1}^{k} \begin{pmatrix}m_i\\n_i\end{pmatrix} \qquad \left ( mod \;\; p \right ) (mn?)≡i=1∏k?(mi?ni??)(modp)
??其中 m i m_i mi?和 n i n_i ni?分別是m和n的p進制表示法中的各位數字，當m<n時，二項式系數 ( m n ) \begin{pmatrix}m\\n\end{pmatrix} (mn?)規定為0。因此，若 ( m n ) \begin{pmatrix}m\\n\end{pmatrix} (mn?)是p的倍數，則至少存在一個 n i > m i n_i>m_i ni?>mi?。反之，若 ( m n ) \begin{pmatrix}m\\n\end{pmatrix} (mn?)不是p的倍數，則所有 n i ≤ m i n_i≤m_i ni?≤mi?必須都成立。
??由此可見，對輸入N，求出其P進制表示法中的各位數字 N i N_i Ni?，則楊輝三角第N+1行中不能整除P的數有 ∏ ( N i + 1 ) \prod \left ( N_i + 1 \right ) ∏(Ni?+1)個。
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;
}
