[GDKOI2016]小学生数学题

[GDKOI2016]小学生数学题

题意：给定n、p、k，求$\sum_{i=1}^n \frac 1i(mod\ p^k)$∑i=1n​i1​(mod pk)

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

对于 $\frac 1{i+jp}$i+jp1​的化简，可以用牛顿二项式定理
$(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$(i+jp)−1=∑l=0∞​C−1l​i−1−l(jp)l=∑l=0k−1​C−1l​i−1−l(jp)l
在模 $p^k$pk 的情况下，只需要处理到 $k-1$k−1 就可以了，后面的都是整除的。
$g(n,k)=\sum_{i=1}^{p-1}\sum_{j=0}^{\lfloor \frac np\rfloor-1} \sum_{l=0}^{k-1} -1^l i^{-1-l}{(jp)}^l$g(n,k)=i=1∑p−1​j=0∑⌊pn​⌋−1​l=0∑k−1​−1li−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 np\rfloor-1}j^l$g(n,k)=i=1∑p−1​l=0∑k−1​−1lil+1pl​j=0∑⌊pn​⌋−1​jl

因此$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 np\rfloor-1}j^l+\sum_{i=n-\lfloor \frac np \rfloor \times p}^n \frac 1i$G(n,k)=i=1∑p−1​l=0∑k−1​−1lil+1pl​j=0∑⌊pn​⌋−1​jl+i=n−⌊pn​⌋×p∑n​i1​

而$F(n,k)=\sum_{i=1}^{\lfloor \frac np \rfloor} \frac 1{ip}+G(n,k)$F(n,k)=i=1∑⌊pn​⌋​ip1​+G(n,k)

提取p化简：
$F(n,k)=\frac 1p\sum_{i=1}^{\lfloor \frac np \rfloor} \frac 1{i}+G(n,k)$F(n,k)=p1​i=1∑⌊pn​⌋​i1​+G(n,k)

注意这里是模p^k意义下的，不能直接就等价于$F(\lfloor \frac np \rfloor,k)$F(⌊pn​⌋,k)

$a\ mod\ b =\frac {ap \mod bp}p$a mod b=papmodbp​

因此 $F(n,k)=F(\lfloor \frac np \rfloor,k+1)+G(n,k)$F(n,k)=F(⌊pn​⌋,k+1)+G(n,k)