[GDKOI2016]小学生数学题

题意：给定n、p、k，求${\sum }_{i=1}^n\frac{1}{i}(mod{p}^k)$

思路：设$f(n,k)={\sum }_{i=1}^n\frac{1}{i}(mod{p}^k)$
一个整数a关于模数p存在逆元的条件是a、p互质，因此需要分类讨论i是否能被p整除。
分成两部分，一部分能被p整除，另一部分不能被p整除，设为G(n,k)
$$G(n,k)=\sum _{i=1}^{p-1}\sum _{j=0}^{\lfloor \frac{n}{p}\rfloor -1}\frac{1}{i+jp}+\sum _{i=n-\lfloor \frac{n}{p}\rfloor \times p}^n\frac{1}{i}$$
主要化简左边部分，设为$g(n,k)$

对于 $\frac{1}{i+jp}$的化简，可以用牛顿二项式定理
$(i+jp{)}^{-1}={\sum }_{l=0}^{\infty }{C}_{-1}^l{i}^{-1-l}{(jp)}^l={\sum }_{l=0}^{k-1}{C}_{-1}^l{i}^{-1-l}{(jp)}^l$
在模 $p^k$ 的情况下，只需要处理到 $k-1$ 就可以了，后面的都是整除的。
$$g(n,k)=\sum _{i=1}^{p-1}\sum _{j=0}^{\lfloor \frac{n}{p}\rfloor -1}\sum _{l=0}^{k-1}-1^l{i}^{-1-l}{(jp)}^l$$
$$g(n,k)=\sum _{i=1}^{p-1}\sum _{l=0}^{k-1}-1^l\frac{p^l}{i^{l+1}}\sum _{j=0}^{\lfloor \frac{n}{p}\rfloor -1}{j}^l$$

因此$$G(n,k)=\sum _{i=1}^{p-1}\sum _{l=0}^{k-1}-1^l\frac{p^l}{i^{l+1}}\sum _{j=0}^{\lfloor \frac{n}{p}\rfloor -1}{j}^l+\sum _{i=\lfloor \frac{n}{p}\rfloor \times p+1}^n\frac{1}{i}$$

而$$F(n,k)=\sum _{i=1}^{\lfloor \frac{n}{p}\rfloor }\frac{1}{ip}+G(n,k)$$

提取p化简：
$$F(n,k)=\frac{1}{p}\sum _{i=1}^{\lfloor \frac{n}{p}\rfloor }\frac{1}{i}+G(n,k)$$

注意这里是模p^k意义下的，不能直接就等价于$F(\lfloor \frac{n}{p}\rfloor ,k)$

$$amodb=\frac{ap\mathrm{m}\mathrm{o}\mathrm{d}bp}{p}$$

因此 $F(n,k)=\frac{F(\lfloor \frac{n}{p}\rfloor ,k+1)}{p}+G(n,k)$

参考博客：
最好https://blog.csdn.net/doyouseeman/article/details/50808852
https://www.cnblogs.com/maijing/p/5240191.html
https://blog.csdn.net/weixin_30882895/article/details/99402693