专业做网站和小程序,海尔公司的网站建设,django的优点,潍坊网站建设工作室杜教筛入门
前置知识
迪利克雷卷积#xff08;*#xff09;#xff1a;
先介绍三个重要的函数#xff1a; 元函数ϵ(n)[n1]\epsilon(n) [n 1]ϵ(n)[n1] 原函数可以看成是迪利克雷卷积里的单位元#xff0c;即(ϵ∗f)(n)f(n)(\epsilon * f)(n) f(n)(ϵ∗f)(n)f(n)*
先介绍三个重要的函数 元函数ϵ(n)[n1]\epsilon(n) [n 1]ϵ(n)[n1] 原函数可以看成是迪利克雷卷积里的单位元即(ϵ∗f)(n)f(n)(\epsilon * f)(n) f(n)(ϵ∗f)(n)f(n) 证明(ϵ∗f)(n)∑d∣nϵ(d)f(nd)ϵ(1)f(n)f(n)(\epsilon * f)(n) \sum_{d \mid n} \epsilon(d) f(\frac{n}{d}) \epsilon(1)f(n) f(n)(ϵ∗f)(n)∑d∣nϵ(d)f(dn)ϵ(1)f(n)f(n) 恒等函数I(n)1I(n) 1I(n)1通俗来讲就是其值恒为1 单位函数id(n)nid(n) nid(n)n
卷积的定义(f∗g)(n)∑d∣nf(d)g(nd)(f*g)(n) \sum_{d \mid n} f(d)g(\frac{n}{d})(f∗g)(n)∑d∣nf(d)g(dn)
并且这个式子是满足交换律结合律分配律的。
与莫比乌斯函数有关的卷积
∑d∣nμ(d)[n1]\sum_{d \mid n} \mu(d) [n 1]∑d∣nμ(d)[n1]
写成卷积也就是(I∗μ)(n)ϵ(n)[n1](I * \mu)(n) \epsilon(n) [n 1](I∗μ)(n)ϵ(n)[n1]。
与欧拉函数有关的卷积
∑d∣nϕ(d)n\sum_{d \mid n} \phi(d) n∑d∣nϕ(d)n
写成卷积就是(I∗ϕ)(n)id(n)(I * \phi)(n) id(n)(I∗ϕ)(n)id(n)。
正式开始了
所谓杜教筛就是可以在n23n ^ \frac{2}{3}n32的时间复杂度内算出积性函数的浅醉和来所以当数据≥1e8\geq 1e8≥1e8的时候就只能用杜教筛了。
假设有积性函数f(n)f(n)f(n)我们要求S(n)∑i1nf(i)n≤1e10S(n) \sum\limits_{i 1} ^{n}f(i)n \leq 1e10S(n)i1∑nf(i)n≤1e10。
根据迪利克雷卷积我们引入一个新的积性函数g(n)g(n)g(n)F(n)(g∗f)(n)F(n) (g * f)(n)F(n)(g∗f)(n) ∑i1nF(i)∑i1n(g∗f)(i)∑i1n∑d∣ig(d)f(id)∑d1ng(d)∑d∣if(id)∑d1ng(d)∑i1ndf(i)∑d1ng(d)S(nd)\sum_{i 1} ^{n} F(i) \sum_{i 1} ^{n} (g * f)(i) \sum_{i 1} ^{n} \sum_{d \mid i} g(d)f(\frac{i}{d})\\ \sum_{d 1} ^{n} g(d) \sum_{d \mid i} f(\frac{i}{d}) \sum_{d 1} ^{n} g(d) \sum_{i 1} ^{\frac{n}{d}}f(i)\\ \sum_{d 1} ^{n} g(d) S(\frac{n}{d})\\ i1∑nF(i)i1∑n(g∗f)(i)i1∑nd∣i∑g(d)f(di)d1∑ng(d)d∣i∑f(di)d1∑ng(d)i1∑dnf(i)d1∑ng(d)S(dn) 所以有∑i1nF(i)g(1)S(n)∑d2ng(d)S(nd)\sum\limits_{i 1} ^{n} F(i) g(1)S(n) \sum_{d 2} ^{n} g(d) S(\frac{n}{d})i1∑nF(i)g(1)S(n)∑d2ng(d)S(dn)
积性函数的定义有g(1)1g(1) 1g(1)1所以接下来
S(n)∑i1nF(i)−∑d2ng(d)S(nd)S(n) \sum\limits_{i 1} ^{n} F(i) - \sum\limits_{d 2} ^{n}g(d)S(\frac{n}{d})S(n)i1∑nF(i)−d2∑ng(d)S(dn)
如果我们能够较快速的计算出∑i1n(g∗f)(i)\sum\limits_{i 1} ^{n} (g * f)(i)i1∑n(g∗f)(i)这个问题就可以通过数论分块很好的解决了当然在次之前我们还得预先筛选出前n23n ^{\frac{2}{3}}n32的前缀和来然后再通过记忆化搜索去得到答案。
几个例子
一、求S(n)∑i1nμ(i)S(n) \sum\limits_{i 1} ^{n} \mu(i)S(n)i1∑nμ(i)
我们先套用上面的式子S(n)∑i1ng∗μ−∑d2ng(d)S(nd)S(n) \sum\limits_{i 1} ^{n} g * \mu - \sum\limits_{d 2} ^{n}g(d)S(\frac{n}{d})S(n)i1∑ng∗μ−d2∑ng(d)S(dn)
我们考虑到I∗μϵI * \mu \epsilonI∗μϵ于是我们得到S(n)∑i1nϵ−∑d2nS(nd)1−∑d2nS(nd)S(n) \sum\limits_{i 1} ^{n}\epsilon - \sum\limits_{d 2} ^{n} S(\frac{n}{d}) 1 - \sum\limits_{d 2} ^{n} S(\frac{n}{d})S(n)i1∑nϵ−d2∑nS(dn)1−d2∑nS(dn)
于是我们就完美解决了这个问题。
二、求S(n)∑i1niμ(i)S(n) \sum\limits_{i 1} ^{n} i \mu(i)S(n)i1∑niμ(i)
上面式子按照套路模板写下来S(n)∑i1ng∗μ∗id−∑d2ng(d)S(nd)S(n) \sum\limits_{i 1} ^{n} g * \mu *id - \sum\limits_{d 2} ^{n}g(d)S(\frac{n}{d})S(n)i1∑ng∗μ∗id−d2∑ng(d)S(dn)
同样的有μ∗Iϵϵ∗idid\mu * I \epsilon\epsilon *id idμ∗Iϵϵ∗idid
所以我们得到S(n)∑i1ni−∑d2nS(nd)S(n) \sum\limits_{i 1} ^{n}i - \sum\limits_{d 2} ^{n}S(\frac{n}{d})S(n)i1∑ni−d2∑nS(dn)
貌似推得很有道理所以我们错在哪
事实上我们模板都抄错了iμ(i)i \mu(i)iμ(i)这东西显然不是迪利克雷卷积
我们设f(n)nμ(n)f(n) n \mu(n)f(n)nμ(n)所以g∗f∑d∣nf(d)g(nd)∑d∣ndμ(d)g(nd)g * f \sum_{d \mid n} f(d) g(\frac{n}{d}) \sum_{d \mid n} d \mu(d) g(\frac{n}{d})g∗f∑d∣nf(d)g(dn)∑d∣ndμ(d)g(dn)
容易想到∑d∣nμ(d)[n1]\sum_{d \mid n} \mu(d) [n 1]∑d∣nμ(d)[n1]所以从这点出发我们考虑dg(nd)μ(d)d g(\frac{n}{d}) \mu(d)dg(dn)μ(d)如何得到含有μ(d)\mu(d)μ(d)的形式。
显然通过观察如果我们让g(n)ng(n) ng(n)n上式就有dg(nd)μ(d)dndμ(d)nμ(d)d g(\frac{n}{d}) \mu(d) d \frac{n}{d} \mu(d) n\mu(d)dg(dn)μ(d)ddnμ(d)nμ(d)
带入原式子就变成了S(n)∑i1n∑d∣iiμ(d)−∑d2ndS(nd)∑i1ni∑d∣iμ(d)−∑d2ndS(nd)∑i1ni(i1)−∑d2ndS(nd)S(n) \sum\limits_{i 1} ^{n} \sum\limits_{d \mid i}i \mu(d) - \sum\limits_{d 2} ^{n}d S(\frac{n}{d}) \sum\limits_{i 1} ^{n} i\sum\limits_{d \mid i}\mu(d) - \sum\limits_{d 2} ^{n}d S(\frac{n}{d}) \sum\limits_{i 1} ^{n} i(i 1) - \sum\limits_{d 2} ^{n}d S(\frac{n}{d})S(n)i1∑nd∣i∑iμ(d)−d2∑ndS(dn)i1∑nid∣i∑μ(d)−d2∑ndS(dn)i1∑ni(i1)−d2∑ndS(dn)
由此我们成功推出S(n)1−∑d2ndS(nd)S(n) 1 - \sum\limits_{d 2} ^{n} d S(\frac{n}{d})S(n)1−d2∑ndS(dn)。
三、求S(n)∑i1nϕ(i)S(n) \sum\limits_{i 1} ^{n} \phi(i)S(n)i1∑nϕ(i)
直接套就行了这个S(n)∑i1ng∗phi−∑d2ng(d)S(nd)S(n) \sum\limits_{i 1} ^{n} g * phi - \sum\limits_{d 2} ^{n}g(d)S(\frac{n}{d})S(n)i1∑ng∗phi−d2∑ng(d)S(dn)
有I∗ϕidI * \phi idI∗ϕid所以S(n)∑i1ni−∑d2nS(nd)S(n) \sum\limits_{i 1} ^{n} i - \sum\limits_{d 2} ^{n}S(\frac{n}{d})S(n)i1∑ni−d2∑nS(dn)
就直接推出来了。
四、求S(n)∑i1niϕ(i)S(n) \sum\limits_{i 1} ^{n} i \phi(i)S(n)i1∑niϕ(i)
仿照二先推出一个ggg出来
f∗g∑d∣nf(d)g(nd)∑d∣ndϕ(d)g(nd)f * g \sum_{d \mid n} f(d) g(\frac{n}{d}) \sum_{d \mid n} d \phi(d) g(\frac{n}{d})f∗g∑d∣nf(d)g(dn)∑d∣ndϕ(d)g(dn)
同样联想∑d∣nϕ(d)n\sum_{d \mid n} \phi(d) n∑d∣nϕ(d)n所以我们同样地取g(n)nidg(n) n idg(n)nid
就有f∗g∑d∣nnϕ(d)f * g \sum_{d \mid n} n \phi(d)f∗g∑d∣nnϕ(d)
带入杜教筛式子就有S(n)∑i1ni∑d∣iϕ(d)−∑d2ndS(nd)S(n)∑i1ni2−∑d2ndS(nd)S(n) \sum\limits_{i 1} ^{n} i \sum\limits_{d \mid i} \phi(d) - \sum\limits_{d 2} ^{n}dS(\frac{n}{d}) S(n) \sum\limits_{i 1} ^{n} i ^ 2 - \sum\limits_{d 2} ^{n}dS(\frac{n}{d})S(n)i1∑nid∣i∑ϕ(d)−d2∑ndS(dn)S(n)i1∑ni2−d2∑ndS(dn)
