HDU 6440 – Dream

题目链接:HDU 6440 | CCPC 2018 网络选拔赛[C] – Dream

方法一

考虑当$p$为一个素数且$n \neq p, n \neq 0$,$C_{p}^{n} = \frac{p!}{n!(p-n)!} = \frac{p\cdot (p-1)\cdot (p-2)…(p-n+1)}{n\cdot (n-1)\cdot (n-2)…1}$ ,分子上的$p$是不会被约掉的,所以$p|C_{p}^{n}$。$(*)$

对$(m+n)^p$作二项式展开,则

$$(m+n)^p=\sum_{i=0}^{p} C_{p}^{i}m^in^{p-i}=C_{p}^{0} m^0 n^p+C_{p}^{p} m^0 n^p+ \sum_{i=1}^{p-1} C_{p}^{i}m^in^{p-i}=m^p+n^p+\sum_{i=1}^{p-1} C_{p}^{i}m^in^{p-i}$$

对比目标式$(m+n)^p=m^p+n^p$,我们需要$\sum_{i=1}^{p-1} C_{p}^{i}m^in^{p-i}=0$,根据(*)可知$\sum_{i=1}^{p-1} C_{p}^{i}m^in^{p-i} \mod p=0$,所以可以构造成模p乘法和模p加法。

方法二

官方题解:

根据费马小定理,$p$为素数时,$a^p \equiv a (\mod p)$,那么

$$(m+n)^p \equiv m+n \equiv m^p + n^p(\mod p)$$

$$(m+n)^p \mod p = (m^p + n^p)\mod p$$

所以构造模p乘法和模p加法。

(其实方法一就是费马小定理的证明方法之一,Bin神的ACM交流群里有大佬说和循环群有关?所以应该还有别的方法)

代码

 

 

说点什么

avatar
50
  Subscribe  
提醒