看英文看到想睡覺… 再來打個之前看過的題目好了。
台大資工2008
\([\frac{10^{10000}}{10^{100}+7}]\) 除以100的餘數為何([]是高斯符號)?
解法如下:
令\(x=10^{100}\),原式即為: \[ \begin{align} & [\frac{x^{100}}{x+7}]\\ = & [\frac{x^{100} -7^{100}}{x+7}+\frac{7^{100}}{x+7}]\\ = & \frac{x^{100} -7^{100}}{x+7}\\ = & \sum_{n=0}^{99} {99 \choose n} x^{n}(-7)^{99-n} \end{align} \] 去掉高斯的原因是因為\(\frac{7^{100}}{x+7}\in (0,1)\) 且\(\frac{x^{100} -7^{100}}{x+7}=\sum_{n=0}^{99} {99 \choose n} x^{n}(-7)^{99-n}\)為整數。
再取\(\mod 100\), \[ \begin{align} & [\frac{10^{10000}}{10^{100}+7} ] \mod 100\\ = &\sum_{n=0}^{99} {99 \choose n} 10^{100n}(-7)^{99-n} \mod 100\\ = & (-7)^{99} \mod 100\\ = & (-7)^3 \cdot 2401^{24} \mod 100\\ = & -343 \mod 100\\ = & 57 \end{align} \]