首页 > 其他 > 详细

一道题2

时间:2018-01-18 20:14:57      阅读:193      评论:0      收藏:0      [点我收藏+]

求:$\sum_{m=1}^{n}\sum_{p=1}^{M}\sum_{q=p+1}^{M}[(p,q)=1][p+q\geqslant M]\frac{1}{pq}$保留四位小数,$n\leqslant 1e7$。

$\sum_{M=1}^{n}\sum_{p=1}^{M}\sum_{q=p+1}^{M}[(p,q)=1][p+q\geqslant M]\frac{1}{pq}$

闪一句,重要套路:$\sum_{a,b}\epsilon ((a,b))=\sum_{d|a,d|b}\mu(d)$,然后把$\mu(d)$提前面去算系数。

$=\sum_{M=1}^{n}\sum_{p=1}^{M}\sum_{q=p+1}^{M}[p+q\geqslant M]\frac{1}{pq}\sum_{d|p,d|q}\mu(d)$

闪一句:这里易错,不是$\sum_{p=1}^{M}\sum_{q=p+1}^{M}[(p,q)=d]$,而是$\sum_{p=1}^{M}\sum_{q=p+1}^{M}[d|(p,q)]$。

$=\sum_{M=1}^{n}\sum_{d=1}^{M}\mu(d)\sum_{p=1}^{M}\sum_{q=p+1}^{M}\frac{1}{pq}[p+q\geqslant M]$

闪一句:这里压p,q的边界,把条件写草稿纸上确定新的变量的取值范围。

$=\sum_{M=1}^{n}\sum_{d=1}^{M}\mu(d)\sum_{x=1}^{\left \lfloor \frac{M}{d} \right \rfloor}\sum_{y=x+1}^{\left \lfloor \frac{M}{d} \right \rfloor}\frac{1}{xyd^2}[xd+yd\geqslant M]$

闪一句:这里易错,两边除一个数时记得判断是否整除会不会对答案有影响。

下面这句之所以这么变:

$M \ \ mod \ \ d=0$:两边直接除d没啥关系。

$M \ \ mod \ \ d\neq 0$:

$x+y=\left \lfloor \frac{M}{d} \right \rfloor\Rightarrow xd+yd=\left \lfloor \frac{M}{d} \right \rfloor*d<M \ \ (\times )$

$x+y>\left \lfloor \frac{M}{d} \right \rfloor\Rightarrow xd+yd\geqslant (\left \lfloor \frac{M}{d} \right \rfloor+1)*d\geqslant M(\sqrt )$

闪一句:下面继续。

$=\sum_{M=1}^{n}\sum_{d=1}^{M}\frac{\mu(d)}{d^2}\sum_{x=1}^{\left \lfloor \frac{M}{d} \right \rfloor}\sum_{y=x+1}^{\left \lfloor \frac{M}{d} \right \rfloor}\frac{1}{xy}([x+y\geqslant \left \lfloor \frac{M}{d} \right \rfloor]-[x+y=\left \lfloor \frac{M}{d} \right \rfloor][M \ \ mod \ \ d\neq 0])$

闪很多句:这里遇到了一个疑似可以解决(因为题解解决了。。。)的两个小式子:

$T(n)=\sum_{p=1}^{n}\sum_{q=p+1}^{n}[p+q\geqslant n]\frac{1}{pq}$

以及

$G(n)=\sum_{p=1}^{n}\sum_{q=p+1}^{n}[p+q=n]\frac{1}{pq}$.

先看$G(n)$:

$G(n)=\sum_{p=1}^{n}\sum_{q=p+1}^{n}[p+q=n]\frac{1}{pq}$

$=\frac{1}{2}(\sum_{p=1}^{n-1}\frac{1}{p(n-p)}-\frac{1}{(\frac{n}{2})^2}[n \ \ mod \ \ 2=0])$

$=\frac{1}{2}(\sum_{p=1}^{n-1}\frac{1}{n}(\frac{1}{p}+\frac{1}{n-p})-\frac{4}{n^2}[n \ \ mod \ \ 2=0])$

$=\frac{1}{2}(2\sum_{p=1}^{n-1}\frac{1}{np}-\frac{4}{n^2}[n \ \ mod \ \ 2=0])$

$=\frac{F(n-1)}{n}-\frac{2}{n^2}[n \ \ mod \ \ 2=0]$

这里$F(n)=\sum_{p=1}^{n}\frac{1}{p}$.

$T(n)=\sum_{p=1}^{n}\sum_{q=p+1}^{n}[p+q\geqslant n]\frac{1}{pq}$

$=\sum_{p=1}^{n-1}\sum_{q=p+1}^{n-1}\frac{1}{pq}([p+q\geqslant n-1]-[p+q=n-1])+\sum_{p=1}^{n-1}\frac{1}{np}$

$=T(n-1)-G(n-1)+\frac{F(n-1)}{n}$.

OK那我们继续:

$S(n)=\sum_{M=1}^{n}\sum_{d=1}^{M}\frac{\mu(d)}{d^2}\sum_{x=1}^{\left \lfloor \frac{M}{d} \right \rfloor}\sum_{y=x+1}^{\left \lfloor \frac{M}{d} \right \rfloor}\frac{1}{xy}([x+y\geqslant \left \lfloor \frac{M}{d} \right \rfloor]-[x+y=\left \lfloor \frac{M}{d} \right \rfloor][M \ \ mod \ \ d\neq 0])$

$=\sum_{M=1}^{n}\sum_{d=1}^{M}\frac{\mu(d)}{d^2}(T(\left \lfloor \frac{M}{d} \right \rfloor)-G(\left \lfloor \frac{M}{d} \right \rfloor)[M \ \ mod \ \ d\neq 0])$

闪一句:对每一个d,所有M:$d\leqslant M\leqslant n$都会被枚举到。因此

$=\sum_{d=1}^{n}\frac{\mu(d)}{d^2}\sum_{M=d}^{n}(T(\left \lfloor \frac{M}{d} \right \rfloor)-G(\left \lfloor \frac{M}{d} \right \rfloor)[M \ \ mod \ \ d\neq 0])$。

枚举倍数,$nln(n)$搞定。

话说有$O(n)$做法,但是。。等我心情平复了再来看。

一道题2

原文:https://www.cnblogs.com/Blue233333/p/8312552.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!