2
14
2016
3

论逗逼的自我修养之寒假颓废记

寒假一直在浪浪浪,起点文看看钱骗骗...后来听说唐老师发了一篇关于杜教筛的博客,于是就去学姿势啦..

感觉这些问题还是非常有趣的..所以就写篇博客来装作自己的寒假没有被浪掉好啦。

唐老师的博客地址在这里http://blog.csdn.net/skywalkert/article/details/50500009

嘛..有一类问题差不多长这样:

首先,出题人不知道干了些什么,YY出了一下奇怪的函数[tex]f(x)[/tex],正常点的话有[tex]\mu(x)[/tex],[tex]\phi(x)[/tex],有些时候也有一些奇形怪状的函数比如[tex]f(n)=\prod (p_i^{a_i}+1)[/tex],其中[tex]p_i[/tex]是质数,[tex]a_i>0[/tex]且[tex]n=\prod p_i^{a_i}[/tex]。

接着,出题人给了你一个挺大的[tex]n[/tex],[tex]n[/tex]一般来说都有[tex]10^{10}[/tex]左右。

最后,他想让你输出[tex]\sum_{i=1}^n f(i)[/tex]的值(可能会对一个大数取模)。

杜教筛差不多就是拿来解决这类问题哒..它给出了一个比较通用的技巧使得可以在[tex]O(n^{\frac{2}{3}})[/tex]或者[tex]O(n^{\frac{3}{4}})[/tex]的时间复杂度内求的答案。

比如我们现在要求[tex]S(n)=\sum_{i=1}^n f(i)[/tex],可能直接求非常困难,可以采用的一个方法是找出另外一个函数[tex]g(x)[/tex],我们考虑[tex](f*g)(x)[/tex]的前缀和:

[tex]\sum_{i=1}^n \sum_{j|i} f(\frac{i}{j})g(j)=\sum_{ij\leq n}f(i)g(j)=\sum_{i=1}^n g(i)S(\lfloor \frac{n}{i} \rfloor)[/tex]

这样我就得到了一个关于[tex]S(n)[/tex]的递推式:

[tex]g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^ng(i)S(\lfloor \frac{n}{i} \rfloor)[/tex]

如果[tex](f*g)(x)[/tex]的前缀和以及[tex]g(x)[/tex]的前缀和都很好计算,那么我们可以直接通过这个递推式来一波记忆搜,这样的复杂度是[tex]O(n^{\frac{3}{4}})[/tex]的,如果我们对不超过[tex]\sqrt n[/tex]的[tex]x[/tex]都预处理[tex]S(x)[/tex],那么复杂度就是[tex]O(n^{\frac{2}{3}})[/tex]啦。

通过这种方法,我们非常容易的求出[tex]\mu(x)[/tex]和[tex]\phi(x)[/tex]的前缀和(让[tex]g(x)=1[/tex]即可)。但是通常题目中的函数都不会那么简单,而对于较复杂一点的函数有这样两个比较基本的形式:

1.求[tex]S(n)=\sum_{i=1}^n (f \cdot g)(i)[/tex]的值且[tex]g(x)[/tex]为完全积性函数。这时有:

[tex]S(n)=\sum_{i=1}^n[(f*1) \cdot g](i)-\sum_{i=2}^n S(\lfloor \frac{n}{i} \rfloor)g(i)[/tex]

2.求[tex]S(n)=\sum_{i=1}^n (f*g)(i)[/tex]的值。这时有:

[tex]S(n)=\sum_{i=1}^n g(i)\sum_{ij \leq n}(f*1)(j)-\sum_{i=2}^n S(\lfloor \frac{n}{i} \rfloor)[/tex]

用这几个工具,就能非常轻易的解决一些这一类问题啦..接下来是几个栗子(其实都是从唐老师博客下面抓来的):

【例1】求[tex]\sum_{i=1}^n\sum_{j=1}^n \text{lcm}(ij)[tex]。

首先先对这个柿子进行化简:

[tex]A(n)=\sum_{i=1}^n\text{lcm}(in)=n\sum_{i=1}^n\frac{i}{(n,i)}=n\sum_{d|n}\sum_{id\leq n}i[(i,\frac{n}{d})=1][/tex]

因为有[tex]\sum_{i=1}^n i[(i,n)=1]=\frac{1}{2}([n=1]+n\phi(n))[/tex],所以我们实际要求的是[tex]B(n)=n\sum_{d|n}d\phi(d)[/tex]的前缀和,即求[tex]id \cdot [(id \cdot \phi) * 1][/tex]的前缀和。

这儿有两种处理方法。第一种如下:

[tex]\sum_{i=1}^n B(i)=\sum_{i=1}^ni\sum_{j|i}j\phi(j)=\sum_{i=1}^n i^2 \phi(i) \sum_{ij\leq n}j[/tex]

可以发现[tex]\sum_{ij\leq n}j[/tex]的柿子只有[tex]O(\sqrt n)[/tex]种取值。所以问题就转化成了对所有的[tex]i[/tex],求出[tex]id^2 \cdot \phi[/tex]的前[tex]\lfloor \frac{n}{i} \rfloor[/tex]项的和。这只需要直接套用[tex]f(x) \cdot g(x)[/tex]的公式就好啦。

接着来分析复杂度,可以发现在求解前[tex]n[/tex]项的前缀和的时候,我们已经对所有的[tex]i[/tex]都求出来了前[tex]\lfloor \frac{n}{i} \rfloor[/tex]项的和,所以时间复杂度和只求一次是完全一样的。

第二种处理方法如下:

[tex]id \cdot [(id \cdot \phi) * 1]=(id^2 \cdot \phi) * id[/tex]

我们采用最原始的方法,给这个函数卷上[tex]id^2[/tex],那么就有:

[tex](id^2 \cdot \phi) * id * id^2=[(id^2 \cdot \phi)*id^2]*id=id \cdot (id^2 * 1)[/tex]

这个柿子的前缀和是非常好求的,所以直接套用前面的公式就可以解决了。

【例2】求[tex]S(n)=\sum_{i=1}^n\sum_{j=1}^n f(ij)[/tex]。其中[tex]f(x)[/tex]指[tex]x[/tex]的约数个数。

可以直接套用陈老师r老师等式:

[tex]S(n)=\sum_{i=1}^n\sum_{j=1}\lfloor \frac{n}{i} \rfloor \lfloor \frac{n}{j} \rfloor [(i,j)=1][/tex]

然后反演一下可以得到:

[tex]S(n)=\sum_{d=1}^n\mu(i)(\sum_{id \leq n}\lfloor \frac{n}{id} \rfloor)^2[/tex]

可以发现后半部分的取值只有[tex]O(\sqrt n)[/tex]种,每一段分别求[tex]\mu(i)[/tex]的前缀和就行了。

【例3】求[tex]S(n)=\sum_{i=1}^n\sum_{j=1}^n f(ij)[/tex]。其中[tex]f(x)[/tex]指[tex]x[/tex]的约数和。

因为有[tex]f(ij)=\sum_{a|i}\sum_{b|j}\frac{aj}{b}[(a,b)=1][/tex],所以就可以将柿子化简然后反演一波得到:

[tex]S(n)=\sum_{d=1}^n \mu(k)k\sum_{ak \leq n}\sum_{aki \leq n}a \sum_{bk \leq n} \sum_{bkj \leq n}j[/tex]

可以发现后半部分的两个柿子的取值都只有[tex]O(\sqrt n)[/tex]种,每一段分别求[tex]\mu(i)i[/tex]的前缀和就行了。

【例4】求[tex]f(n)=\prod (p_i^{a_i}+1)[/tex]的前缀和,其中[tex]p_i[/tex]是质数,[tex]a_i>0[/tex]且[tex]n=\prod p_i^{a_i}[/tex]

观察[tex]f(n)[/tex]可以发现[tex]f(n)=\sum_{i|n}i[(i,\frac{n}{i})=1][/tex],于是就有:

[tex]S(n)=\sum_{i=1}^n f(i)=\sum_{i=1}^ni\sum_{ij \leq n}[(i,j)=1][/tex]

这个时候有两种处理方法,第一种是将这个柿子反演:

[tex]S(n)=\sum_{i=d}^n \mu(d)d \sum_{id \leq n}i\lfloor \frac{n}{id} \rfloor[/tex]

这样就能直接求解了,但是这样常数比较大。第二种方法是暴力容斥,枚举[tex]i[/tex]和[tex]j[/tex]的公约数:

[tex]S(n)=\sum_{ij \leq n}i-\sum_{k=2}^nkS(\lfloor \frac{n}{k^2} \rfloor)[/tex]

显然[tex]k[/tex]不能超过[tex]\sqrt n[/tex],所以直接记忆搜即可。

【例5】求[tex]f(n)=\prod (p_i^{a_i}-1)[/tex]的前缀和,其中[tex]p_i[/tex]是质数,[tex]a_i>0[/tex]且[tex]n=\prod p_i^{a_i}[/tex]

观察[tex]f(n)[/tex]可以发现[tex]n=\sum_{i|n}f(i)[(i,\frac{n}{i})=1][/tex]。

然后我就不会啦QAQ听说过的都是打表的?如果有老司机想出来非打表做法欢迎来找我讨论owo

Category: 论逗逼的自我修养系列 | Tags: | Read Count: 14756
Avatar_small
indwes edu login 说:
2022年8月19日 08:27

MyIWU is our faculty, staff and student portal. Access the MyIWU Portal. What can I do or find here? Access other applications like Banner Self Service, indwes edu login Gmail 2021. Indiana Wesleyan University Login | IWU Student login Online MyIWU Portal 2021 at IWU Portal https://myiwu.indwes.edu/. It enables online learning for the students and has bridged the gap between the student and teacher. You can sign in to your account.

Avatar_small
Haryana Board Questi 说:
2022年9月02日 23:10

Haryana Board Model Paper 2023 Class 5 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. Haryana Board Question Paper Class 5 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

Avatar_small
Emma 说:
2023年1月22日 01:28

This winter vacation has certainly been a unique one. From reading up on money scams to learning the Du Jiaosai posture, it certainly has been a journey of self-cultivation. The questions that buy cheap diamond rings have arisen during this period of time have been incredibly interesting, and it is commendable that you took the time to document your experiences in a blog post. It is great to see that you have taken an unconventional approach to your winter vacation and have managed to turn it into a learning experience.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com