精华内容
下载资源
问答
  • 莫比乌斯函数和莫比乌斯反演 前置技能 基础数论内容。 莫比乌斯函数 μ(n)μ(n)就是莫比乌斯函数,如果有: n=∏i=1mpaixi(ai>0)n=∏i=1mpxiai(ai>0) 那么: μ(n)=⎧⎩⎨⎪⎪1(−1)m0n=1∀ai≤1...

    莫比乌斯函数和莫比乌斯反演

    前置技能

    基础数论内容。

    莫比乌斯函数

    μ(n)μ(n)就是莫比乌斯函数,如果有:

    n=i=1mpaixi(ai>0)n=∏i=1mpxiai(ai>0)

    那么:

    μ(n)=1(1)m0n=1ai1otherμ(n)={1n=1(−1)m∀ai≤10other

    莫比乌斯函数有一个很重要的性质,那就是
    d|nμ(d)=[n=1]∑d|nμ(d)=[n=1]

    证明:n=1n=1时显然。

    n=2n=2时考虑有一个ai>1ai>1时显然对答案没有影响,那么答案就是ni=0(1)i(nk)∑i=0n(−1)i(nk),这个显然等于00

    莫比乌斯反演

    若有

    f(x)=d|xg(d)f(x)=∑d|xg(d)


    g(x)=d|xf(d)μ(xd)g(x)=∑d|xf(d)μ(xd)

    然而不知道有啥用……

    例题

    BZOJ 2301

    其实就是求

    i=abj=cd[gcd(i,j)=k]∑i=ab∑j=cd[gcd(i,j)=k]

    二维差分一下,这个就等价于求
    i=1nj=1m[gcd(i,j)=k]i=1n/kj=1m/k[gcd(i,j)=1]∑i=1n∑j=1m[gcd(i,j)=k]∑i=1⌊n/k⌋∑j=1⌊m/k⌋[gcd(i,j)=1]

    ni=1μ(n)=[n=1]∑i=1nμ(n)=[n=1]

    i=1n/kj=1m/kd|i,d|jμ(d)∑i=1⌊n/k⌋∑j=1⌊m/k⌋∑d|i,d|jμ(d)

    优先枚举dd​
    d=1n/kμ(d)i=1n/dkj=1n/dk1∑d=1⌊n/k⌋μ(d)∑i=1⌊n/dk⌋∑j=1⌊n/dk⌋1

    发现后面的一部分其实就是ndkmdk⌊ndk⌋⌊mdk⌋,因此式子就变成了
    d=1n/kμ(d)ndkmdk∑d=1⌊n/k⌋μ(d)⌊ndk⌋⌊mdk⌋

    发现最后面的取值只有O(n)O(n)种,因此可以数论分块得到单次O(n)O(n)

    BZOJ 4407

    i=1nj=1mgcd(i,j)k∑i=1n∑j=1mgcd(i,j)k

    枚举gcd(i,j)gcd(i,j)

    d=1ndki=1nj=1m[gcd(i,j)=d]d=1ndki=1n/dj=1m/d[gcd(i,j)=1]∑d=1ndk∑i=1n∑j=1m[gcd(i,j)=d]∑d=1ndk∑i=1⌊n/d⌋∑j=1⌊m/d⌋[gcd(i,j)=1]

    发现后面是不是很熟悉?再一次用到那个神奇的公式
    d=1ndki=1n/dj=1m/dx|i,x|jμ(x)∑d=1ndk∑i=1⌊n/d⌋∑j=1⌊m/d⌋∑x|i,x|jμ(x)

    xx提前
    d=1ndkx=1n/dμ(x)i=1n/dxj=1m/dx1d=1ndkx=1n/dμ(x)ndxmdx∑d=1ndk∑x=1⌊n/d⌋μ(x)∑i=1⌊n/dx⌋∑j=1⌊m/dx⌋1∑d=1ndk∑x=1⌊n/d⌋μ(x)⌊ndx⌋⌊mdx⌋

    f(d)=dkn/dx=1μ(x)f(d)=dk∑x=1⌊n/d⌋μ(x),则
    d=1nf(d)ndxmdx∑d=1nf(d)⌊ndx⌋⌊mdx⌋

    显然f(d)f(d)是一个积性函数,那么我们先线筛出f(d)f(d),对f(d)f(d)做前缀和,就可以做到单次O(n)O(n)的复杂度了。

    杜教筛

    前置技能

    莫比乌斯反演?

    杜教筛

    一个积性函数f(x)f(x),怎么求前缀和S(x)=xi=1f(x)S(x)=∑i=1xf(x)

    我们找一个积性函数g(x)g(x)(不知道它是啥),将它与f(x)f(x)做一遍卷积:

    (fg)(n)=d|nf(d)g(nd)(f∗g)(n)=∑d|nf(d)g(nd)

    将卷积做一遍前缀和:
    i=1n(fg)(i)=i=1nd|if(d)g(id)=i=1nd|ig(d)f(id)∑i=1n(f∗g)(i)=∑i=1n∑d|if(d)g(id)=∑i=1n∑d|ig(d)f(id)

    后面的部分可以变成
    d=1ng(d)i=1n/df(i)d=1ng(d)S(nd)∑d=1ng(d)∑i=1⌊n/d⌋f(i)∑d=1ng(d)S(⌊nd⌋)

    因此
    i=1n(fg)(i)=d=1ng(d)S(nd)∑i=1n(f∗g)(i)=∑d=1ng(d)S(nd)

    移项

    g(1)S(n)=i=1n(fg)(i)d=2ng(d)S(nd)g(1)S(n)=∑i=1n(f∗g)(i)−∑d=2ng(d)S(nd)

    观察到等式右边第一项就是fgf∗g的前缀和,第二项中S(nd)S(nd)的取值最多只有O(n)O(n)种。

    所以,如果fgf∗g很好求,gg的前缀和很好求,那么我们就可以很快的递归求出S(n)S(n)的值。

    一般是打表算出前几项,然后递归算,注意一定要记忆化(hash/map均可)。

    莫比乌斯函数的前缀和?

    由于

    d|nμ(d)=[n=1]∑d|nμ(d)=[n=1]

    因此我们取g(x)=1g(x)=1,直接代入式子:
    S(n)=1d=2nS(nd)S(n)=1−∑d=2nS(nd)

    欧拉函数?

    由于

    d|nφ(d)=n∑d|nφ(d)=n

    因此取g(x)=1g(x)=1
    S(n)=n×(n+1)2d=2nS(nd)S(n)=n×(n+1)2−∑d=2nS(nd)

    总结

    这些题大概都有套路?推式子的方法感觉都差不多……

    转载于:https://www.cnblogs.com/Canopus-wym/p/10376157.html

    展开全文
  • 杜教筛的套路和莫比乌斯反演很像,都需要对狄利克雷卷积有深刻的理解 熟练的背诵 。 莫比乌斯反演需要找到一个函数 \(\textbf g = \textbf f * \mu\) ,杜教筛则是需要找到一个函数 \(\textbf g\) 使得 \(\sum \...

    这一篇\(\texttt{blog}\)应该算这篇的后续,所以可以先看一下这一篇QwQ

    0. 一些奇奇怪怪的数论函数

    \(\begin{aligned}1. \; & \textbf{1}(x) = 1 \\2. \; & \textbf{id}(x) = x, \textbf{id}^k(x) = x ^ k \\3. \; & \textbf{d}(x) = \sum_{d \mid x} 1 \\4. \; & \sigma(x) = \sum_{d\mid x} d\\ 5. \; & \epsilon(x) = [x = 1]\end{aligned}\)

    1. 狄利克雷卷积

    \(\textbf{h} = \textbf{f} * \textbf{g}\),那么:
    \[ \textbf{h}(x) = \sum_{d\mid x} \textbf{f}(d)\textbf{g}(\frac nd) \]
    到这里我们可以推出一些奇奇怪怪的数论函数关系式:

    \(\begin{aligned}1.\;& \textbf{d} = \textbf 1 * \textbf 1\\ 2.\; & \sigma = \textbf 1 * \textbf{id} \\ 3. \; & \textbf{id} = \textbf 1 * \varphi \\ 4. \; & \sigma = \textbf 1 * \textbf 1 * \varphi = \textbf d * \varphi \end{aligned}\)

    其中第四个是乱搞的(逃

    2. 莫比乌斯反演

    \(\mu * \textbf 1 = \epsilon\),那么设\(\textbf f = \textbf 1 * \textbf g\),则\(\textbf g = \mu * \textbf f\)

    然后没了

    到这里我们又可以推出一些奇奇怪怪的数论函数关系式:

    \(\begin{aligned} 1. \; & \varphi = \textbf{id} * \mu \\ 2. \; & \textbf 1 = \mu * \textbf d \\ 3. \; & \textbf{id} = \sigma * \mu \end{aligned}\)

    后面两个都是乱搞的(逃

    说不定后面两个在杜教筛\(\textbf d\)\(\sigma\)的时候有用(雾

    前人研究了一下\(\mu\),发现这不仅牵涉到数论函数的关系,还发现它是一种特殊的容斥系数。这个特性等下再讲,先看一看\(\mu\)的其它的性质。

    我们研究一下\(\mu\)\(p^k\)处的取值(\(p\)是质数)
    \[ \mu(n) = \begin{cases} 1 & k = 0 \\ -1 & k = 1 \\ 0 & k > 1 \end{cases} \]
    于是就可以非常好的线性筛了。

    至于\(\mu\)如何用容斥的方法理解,不想写了可以看yyb的博客

    做题?题目一般会给出求\(\sum_{i=1}^n\sum_{j=1}^m \textbf f(\gcd(i, j))\)

    然后套路就是可以变成\(\sum_{i=1}^n \sum_{j=1}^m \sum_{d | i, d | j} \textbf g(d), \textbf g = \textbf f * \mu\)

    接下来提出\(d\)就可以乱搞了。

    给道例题,就写一道之前那篇文章写的有一点不完全的题目吧。

    给定\(n, m, (n \leq m)\)\(\sum_{i=1}^n\sum_{j=1}^m \sigma(\gcd(i, j))\)

    \(\because \textbf f = \sigma,\therefore \textbf g = \mu * \sigma\)

    之前的g就止步于此

    通过这篇文章的推导,我们翻上面的式子发现\(\mu * \sigma = \textbf{id}\),于是\(\textbf g = \textbf{id}\)

    Wow!

    那么可以推出:
    \[ \begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m \sigma(\gcd(i,j)) \\ =& \sum_{i=1}^n\sum_{j=1}^m\sum_{d|i, d|j} d \\ =& \sum_{d=1}^nd\sum_{d|i}^n\sum_{d|j}^m 1 \\ =& \sum_{d=1}^n d\left\lfloor\frac nd\right\rfloor\left\lfloor\frac md\right\rfloor \end{aligned} \]
    写个鬼的线性筛,直接算不就可以了QwQ

    3. 杜教筛

    用来求积性函数前缀和。即求\(\textbf S(n) = \sum_{i=1}^n \textbf f(i)\)

    假设我们找到了一个有趣的函数\(\textbf g\),使得\(\textbf g\)\(\textbf f * \textbf g\)的前缀和都可以快速求,那么我们可以快速求解\(\textbf S(n)\)
    \[ \begin{aligned} \because \sum_{i=1}^n (\textbf f * \textbf g)(i) &= \sum_{i=1}^n\sum_{d\mid i} \textbf f(d) \textbf g(\frac nd) \\ &= \sum_{d=1}^n \textbf g(d) \sum_{i=1}^{\frac nd} \textbf f(i) \\ &= \sum_{i=1}^n \textbf g(i) \textbf S(\frac ni) \end{aligned} \]
    那么\(\textbf g(1)\textbf S(n) = \sum_{i=1}^n (\textbf f * \textbf g)(i) - \sum_{i=2}^n \textbf g(i) \textbf S(\frac ni)\)

    前一半可以快速求,后一半可以数论分块\(+\)递归求。

    复杂度?\(\mathrm{O}(n ^ {\frac 23})\)或者\(\mathrm{O}(n ^ \frac 34)\),这取决于你的实现方式。

    然后对于\(\sum_{i=1}^n (\textbf f * \textbf g)(i)\)要多快速求呢?首先如果可以\(\mathrm{O}(1)\)算是坠好的,然后我们发现后面要\(\mathrm{O}(\sqrt n)\)的计算,所以这个柿子在\(\mathrm{O}(\sqrt n)\)的时间复杂度内解决也是没有问题的。

    同时这个玩意每次算的值都是一个\(\left\lfloor\frac nx\right\rfloor\),所以求\(\sum_{i=1}^n (\textbf f * \textbf g)(i)\)可以套一个杜教筛。

    同理\(\sum_{i=1}^n \textbf g(i)\)也可以套一层杜教筛,复杂度不会改变。

    杜教筛的套路和莫比乌斯反演很像,都需要对狄利克雷卷积有深刻的理解和熟练的背诵

    莫比乌斯反演需要找到一个函数\(\textbf g = \textbf f * \mu\),杜教筛则是需要找到一个函数\(\textbf g\)使得\(\sum \textbf g(i)\)\(\sum (\textbf f * \textbf g)(i)\)可以快速计算。

    所以上面的那些奇奇怪怪的数论函数关系式要记住。

    举个例子吧,求\(\sum_{i=1}^n \varphi(i)\)

    找到一个函数\(\textbf g\)使得\(\varphi * \textbf g\)可以快速算。

    这个时候我们翻一下上面的式子可以发现\(\varphi * \textbf 1 = \textbf{id}\),然后\(\sum \textbf{id}(i)\)可以快速求,于是就做完了。

    蛤?你说这个例子太简单?那就用一道题目来仔细讲一下这个套路吧。

    洛谷P4213 【模板】杜教筛(Sum)

    洛谷P3768 简单的数学题

    简单写一下题面,求:
    \[ \sum_{i=1}^n\sum_{j=1}^nij\gcd(i,j), n \leq 10^{10} \]
    化式子(这里如果有没看懂的,赶快回去复习一下):
    \[ \begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n ij\gcd(i,j) \\ =& \sum_{i=1}^n\sum_{j=1}^nij\sum_{d|i, d|j} \varphi(d) \\ =& \sum_{d=1}^n\varphi(d)\sum_{d|i}i\sum_{d|j}j \\ =& \sum_{d=1}^n d^2 \varphi(d) S\left(\left\lfloor\frac nd\right\rfloor\right)^2 \end{aligned} \]
    其中\(S(x) = \sum_{i=1}^x i\)

    然后根据之前的套路,我们数论分块,问题转化为如何快速求\(d^2\varphi(d)\)的前缀和。

    首先通过之前杜教筛可以再套杜教筛的理论,这里即使有一个数论分块,复杂度还是\(\mathrm{O}(n^\frac 23)\),于是复杂度是对的,可以放心筛。

    接下来考虑对于\(\textbf f(x) = x^2\varphi(x)\),怎么找到一个合适的函数\(\textbf g\)使得\(\textbf f * \textbf g\)好算。

    定义点积\((\textbf f\cdot\textbf g)(i) = \textbf f(i) \textbf g(i)\),那么我们可以得到一个定理:

    \(\textbf f\)为完全积性函数,\(\textbf g, \textbf h\)是数论函数,那么\((\textbf f \cdot \textbf g) * (\textbf f \cdot \textbf h) = \textbf f \cdot(\textbf g * \textbf h)\)

    证明的话显然。这个定理不就是给我们做题用的吗(逃

    于是对于\(\textbf f = \textbf{id}^2 \cdot \varphi\),可以找到\(\textbf g = \textbf{id}^2 \cdot \textbf 1\),那么\(\textbf f * \textbf g = \textbf{id}^3, \textbf g = \textbf{id}^2\)

    然后就做完了。

    接下来还有贝尔级数等一些鬼畜的高级玩意,直接给链接算了。

    转载于:https://www.cnblogs.com/cj-xxz/p/10587288.html

    展开全文
  • Part0 最近一直在搞这些东西 ...如果您真的想学会莫比乌斯反演和杜教筛,请拿出纸笔,每个式子都自己好好的推一遍,理解清楚每一步是怎么来的,并且自己好好思考。 Part1莫比乌斯反演 莫比乌斯反演啥都没...

    链接:https://blog.csdn.net/qq_30974369/article/details/79087445

    Part0

    最近一直在搞这些东西
    做了将近20道题目吧
    也算是有感而发
    写点东西记录一下自己的感受

    如果您真的想学会莫比乌斯反演和杜教筛,请拿出纸笔,每个式子都自己好好的推一遍,理解清楚每一步是怎么来的,并且自己好好思考。

    Part1莫比乌斯反演

    莫比乌斯反演啥都没有,就只有两个式子(一般只用一个)
    原来我已经写过一次了,再在这里写一次
    就只写常用的那个吧

    基本的公式


    对于一个函数f(x)f(x)
    设g(x)=∑x|df(d)g(x)=∑x|df(d)
    那么

     

    f(x)=∑x|dμ(dx)g(d)f(x)=∑x|dμ(dx)g(d)

     


    这个有什么用?
    似乎太有用了一点

    随手搞道题目来说吧


    ∑i=1n∑j=1m[gcd(i,j)=1]∑i=1n∑j=1m[gcd(i,j)=1]

     

    这个东西很直接,
    所以我们设

    f(x)=∑i=1n∑j=1m[gcd(i,j)=x]f(x)=∑i=1n∑j=1m[gcd(i,j)=x]

     

    g(x)=∑x|df(d)g(x)=∑x|df(d)


    根据莫比乌斯反演可以得到

    f(1)=∑1|dμ(d1)g(d)=∑i=1nμ(i)g(i)f(1)=∑1|dμ(d1)g(d)=∑i=1nμ(i)g(i)


    g(x)g(x) 是什么东西?

    g(x)=∑i=1n∑j=1m[x|gcd(i,j)]g(x)=∑i=1n∑j=1m[x|gcd(i,j)]


    直接把xx 除到上面去

    g(x)=∑i=1n/x∑j=1m/x[1|gcd(i,j)]g(x)=∑i=1n/x∑j=1m/x[1|gcd(i,j)]


    [1|gcd][1|gcd] 显然成立的
    所以g(x)=[nx][mx]g(x)=[nx][mx]
    可以O(1)O(1) 计算
    所以,f(1)f(1) 可以O(n)O(n) 计算

     


    一起推下式子

    莫比乌斯反演的套路太多了

    我们再来看两道题目
    Crash的数字表格
    jzptab

    这两题按照顺序看嗷

    具体的过程直接看我博客里面写的东西

    我们发现这两道题一模一样
    但是下面的那道题目可以做到单次询问O(n−−√)O(n)

    他多干了什么???
    这个问题,我们自己再来重新推一下
    不过找个容易点的东西


     

    ∑i=1n∑j=1mgcd(i,j)∑i=1n∑j=1mgcd(i,j)

     

    这个肯定没有前面我给的例子的莫比乌斯反演那么直接
    但是我们观察一下,gcdgcd 的取值有哪些??
    1~n1~n (假设n<mn<m )
    那么,我们可以把gcdgcd 相同的项合并

    所以,我们枚举gcdgcd 的值

     

    ∑d=1nd∑i=1n∑j=1m[gcd(i,j)=d]∑d=1nd∑i=1n∑j=1m[gcd(i,j)=d]


    后面的那一部分是不是想到了前面推出的东西???
    所以先把dd 直接除上去

    ∑d=1nd∑i=1n/d∑j=1m/d[gcd(i,j)=1]∑d=1nd∑i=1n/d∑j=1m/d[gcd(i,j)=1]


    n/dn/d 和m/dm/d 不要想太多,你就当成xx 和yy

    ∑i=1x∑j=1y[gcd(i,j)=1]∑i=1x∑j=1y[gcd(i,j)=1]


    不就是上面推过的第一个例子??

    =∑i=1xμ(i)[xi][yi]=∑i=1xμ(i)[xi][yi]

     

    把这一截放回我们要求的式子里面去

     

    ∑d=1nd∑i=1xμ(i)[xi][yi]∑d=1nd∑i=1xμ(i)[xi][yi]


    把x,yx,y 还是写成原样吧

    ∑d=1nd∑i=1n/dμ(i)[nid][mid]∑d=1nd∑i=1n/dμ(i)[nid][mid]

     

    是不是n/dn/d 可以数论分块
    而在计算后面的东西的时候,n/din/di 也可以数论分块??
    所以这个时候的复杂度是O(n)O(n)
    与之相对应的就是上面Crash的数字表格的O(n)O(n) 做法

    可是,像下面那个O(n−−√)O(n) 是怎么做的呢?

    那我们就继续推一步
    我们是不是可以直接对nidnid 分块呢?
    所以,我们设T=idT=id 把idid 换一下

     

    ∑d=1nd∑i=1n/dμ(i)[nT][mT]∑d=1nd∑i=1n/dμ(i)[nT][mT]


    这个时候,比较关键的一步
    把TT 提出来

    ∑T=1n[nT][mT]∑d|Tdμ(Td)∑T=1n[nT][mT]∑d|Tdμ(Td)


    为什么是这个??
    我们来分析一波
    首先每一个TT 一定对应[nT][mT][nT][mT]
    这一项之和TT 有关,所以可以提出来

     

    这个时候考虑对于每一个TT ,什么样的ii 和dd 会给他产生贡献呢?
    最显然的一点,dd 是TT 的一个因数
    看到上面的式子,我们不难发现会贡献一个dd 的什么东西
    后面的是什么?μ(i)μ(i)
    继续想想,既然T=idT=id ,我们枚举了一个TT ,
    又知道dd 是TT 的一个因子了,所以i=Tdi=Td
    所以,就有了上面把TT 拿出来的式子

    前面的东西看起来可以数论分块
    但是这样子后面的东西怎么办?
    不可能O(n−−√)O(n) 暴力枚举呀

    没错,当然不需要暴力枚举
    我们发现后面的东西也是一个积性函数(因为他是两个积性函数的狄利克雷卷积)
    所以它是可以线性的筛出来的
    到这里,前面对于TT 数论分块
    后面的前缀和可以O(n)O(n) 线性筛预处理出来
    此时单次询问整体的复杂度就是O(n−−√)O(n)

    对了,不要思想江化
    后面那个东西如果不能够直接线性筛
    那就不要线性筛了,
    只要复杂度允许,暴力筛也是很可以的


    其实,如果我们继续观察,很容易知道一点:
    ∑d|Tdμ(Td)=φ(T)∑d|Tdμ(Td)=φ(T)

    证明?直接从狄利克雷卷积的角度来吧
    我们知道(1∗φ)(i)=i(1∗φ)(i)=i
    还知道(1∗μ)(i)=e(1∗μ)(i)=e
    其中11 是f(x)=1f(x)=1
    ee 是f(x)=[x=1]f(x)=[x=1]
    idid 是f(x)=xf(x)=x
    我们的式子等于
    (id∗φ)(i)=(φ∗1∗μ)(i)=(φ∗(1∗μ))(i)=(φ∗e)(i)=φ(i)(id∗φ)(i)=(φ∗1∗μ)(i)=(φ∗(1∗μ))(i)=(φ∗e)(i)=φ(i)

    所以这个东西当然可以线性筛啦。


    莫比乌斯反演差不多就到这里啦
    我们经历的复杂度从O(n2)O(n2) 的暴力
    推一步之后变成了O(n)O(n)
    再变成了O(n−−√)O(n)

    莫比乌斯反演的关键步骤也就是两步
    首先是化简式子,写成莫比乌斯反演的形式
    然后就是怎么处理前缀和,数论分块等东西的问题

    这些能够解决好,莫比乌斯反演的题目就很好解决啦

    Part2线性筛

    当然是怎么各种线性筛东西啦

    线性筛最重要的一点:
    每个数一定,也只会,被他的最小质因子给筛到
    说白点,比如说72=2∗2∗2∗3∗372=2∗2∗2∗3∗3
    他就会被他的最小质因子给筛到
    也就是2∗362∗36 时被筛到

    所以,一般线性筛如果要存储其他的东西来筛的话
    一定是记录最小质因子的东西

    大概的写一下几个积性函数:

    μμ 莫比乌斯函数

    这个怎么筛应该都会吧

    φφ 欧拉函数

    怎么筛应该也很明显吧。

    dd 约数个数

    这个怎么筛?
    考虑唯一分解定理:
    x=∏paiix=∏piai
    那么d(x)=∏(ai+1)d(x)=∏(ai+1)
    记录一下最小质因子的个数
    每次就先把原来的除掉,再把+1+1 后的个数乘上就好啦

    σσ 约数和

    还是唯一分解定理
    x=∏paiix=∏piai
    σ(x)=∏(∑aij=0pji)σ(x)=∏(∑j=0aipij)
    记录一下最小质因子的上面那个式子的和
    以及这个因子的aiai 次幂
    每次也是先除掉再乘上新的

    akak kk 次幂

    把这个东西写进来,只是为了提醒一下
    akak 这种东西是一个完全积性函数,也是可以丢进去筛的

    invinv 乘法逆元

    没啥,一样的,乘法逆元也是完全积性函数
    蛤,我知道可以O(n)O(n) 递推
    只是写一下而已


    我比较懒,不想把板子蒯过来
    直接把ppl的链接给你们嗷(虽然他的代码风格我觉得很丑)

    Part3杜教筛

    来个栗子

    线性筛O(n)O(n) 复杂度,美滋滋
    好的,我知道了
    来一个很interestinginteresting 的题目???

     

    求∑i=1nμ(i)的值求∑i=1nμ(i)的值

     

    我当然知道你会线性筛
    所以n<=109n<=109

    杜教筛是蛤?

    比如说。。
    我们现在要求一个积性函数f(i)f(i) 的前缀和S(i)S(i)
    也就是说S(n)=∑ni=1f(i)S(n)=∑i=1nf(i)

    现在很不好算呀
    怎么办??

    这个时候,就来杜教筛套路一波

    我再来找个积性函数g(i)g(i) (不知道是啥)
    让gg 和ff 做一个卷积

     

    (g∗f)(i)=∑d|ig(d)f(id)(g∗f)(i)=∑d|ig(d)f(id)


    再求一下卷积的前缀和

    ∑i=1n(g∗f)(i)=∑i=1n∑d|ig(d)f(id)∑i=1n(g∗f)(i)=∑i=1n∑d|ig(d)f(id)


    把dd 给提出来

    ∑d=1ng(d)∑d|if(id)∑d=1ng(d)∑d|if(id)

     

    ∑d=1ng(d)∑i=1n/df(i)∑d=1ng(d)∑i=1n/df(i)

     

    ∑d=1ng(d)S(nd)∑d=1ng(d)S(nd)


    如果仔细想想
    我们就会有这个式子:

    g(1)S(n)=∑i=1ng(i)S(ni)−∑i=2ng(i)S(ni)g(1)S(n)=∑i=1ng(i)S(ni)−∑i=2ng(i)S(ni)


    前面的东西是狄利克雷卷积

    g(1)S(n)=∑i=1n(g∗f)(i)−∑i=2ng(i)S(ni)g(1)S(n)=∑i=1n(g∗f)(i)−∑i=2ng(i)S(ni)


    如果狄利克雷卷积的前缀和非常好算的话
    那么我们就可以对后面的东西进行数论分块
    然后递归计算。
    提醒一句:
    一定要记忆化,一定要记忆化,一定要记忆化

     

    回到栗子

    ∑ni=1μ(i)∑i=1nμ(i)
    把杜教筛的公式套路式子找过来蛤

     

    g(1)S(n)=∑i=1n(g∗μ)(i)−∑i=2ng(i)S(ni)g(1)S(n)=∑i=1n(g∗μ)(i)−∑i=2ng(i)S(ni)


    看到了μμ 想一个积性函数,让他们的狄利克雷卷积前缀和很好算
    我们知道

    ∑d|iμ(d)=[d=1]=e∑d|iμ(d)=[d=1]=e


    也就是说

    (1∗μ)=e(1∗μ)=e


    ee 的前缀和是啥?
    当然是11 了
    所以,取g(x)=1g(x)=1

    S(n)=1−∑i=2nS(ni)S(n)=1−∑i=2nS(ni)


    这样子的话,首先线性筛出一部分的μμ 的前缀和
    然后来一波记忆化搜索美滋滋

     


    再来个栗子把
    把上面的μμ 换成φφ
    我们还是知道

     

    ∑d|iφ(d)=i=id(i)∑d|iφ(d)=i=id(i)


    所以,如果是φφ 的话
    就令g(x)=id(x)=xg(x)=id(x)=x
    所以,

    S(n)=n∗(n+1)2−∑i=2niS(ni)S(n)=n∗(n+1)2−∑i=2niS(ni)

     

    多好的套路

    但是,不要被套路给套死啦
    面对不同的函数
    一定要考虑清楚gg 是啥
    好的gg 能让你的程序更加好算

    Part4我也不知道为什么要加上这一部分

    好啦
    上面好好地写了一下莫比乌斯反演和杜教筛
    是不是觉得很简单

    当然,莫比乌斯反演和杜教筛当然可以混在一起

    莫比乌斯反演推柿子
    杜教筛求前缀和
    一点也不矛盾


    既然我也不知道最后这部分干啥
    那就找一堆题目来吧
    欢迎查我水表
    算了
    还是把水表给你们把
    莫比乌斯反演的水表
    杜教筛的水表


    最后,说几句话
    不要因为有了杜教筛和线性筛
    就天天想着怎么筛
    筛不了就滚去写暴力
    埃氏筛法很不错
    暴力枚举因数也很不错

    展开全文
  • 题目链接题意有∑d|Nf(d)=N2−3N+2\sum_{d|N}f(d)=N^2-3N+2求∑i=1Nf(i)\sum...) 546ms(先感叹一句…我真的是学啥忘啥,看到题目就啥都不想直接杜教筛的方式展开压根就忘了莫比乌斯反演…明明是这么优美的莫比乌斯反演

    题目链接

    题意

    d|Nf(d)=N23N+2
    i=1Nf(i)

    N1e9,答案 mod(1e9+7)

    法一:莫比乌斯反演+杜教筛善后(?) 546ms

    (先感叹一句…我真的是学啥忘啥,看到题目就啥都不想直接杜教筛的方式展开压根就忘了莫比乌斯反演…明明是这么优美的莫比乌斯反演的形式啊)

    推导

    F(n)=n23n+2,则由题意有

    d|Nf(d)=F(N)

    反演得
    d|Nμ(Nd)F(d)=f(N)

    两边求和得
    i=1Nf(i)=i=1Nd|iμ(id)F(d)=k=1Nd=1Nkμ(k)F(d)=i=1Nμ(i)d=1NiF(d)

    分块 O(N) 搞一搞,后面的 F() 求和是 O(1),前面的 μ()1e7 以内预处理,后面杜教筛,就搞定惹。
    杜教筛的部分我上一篇博客里面51nod 1244莫比乌斯函数之和也有写到(包括一些十分基础甚至于愚蠢的推导Orz),当然还是再来推荐一下神犇的浅谈一类积性函数的前缀和 ——skywalkert

    Code

    #include <bits/stdc++.h>
    #define maxn 10000000
    #define maxm maxn + 10
    #include <map>
    using namespace std;
    typedef long long LL;
    const LL mod = 1e9+7;
    map<int, LL> sum;
    int mu[maxm], prime[maxm];
    bool check[maxm];
    LL inv;
    LL poww(LL a, LL b) {
        LL ret = 1;
        while (b) {
            if (b & 1) (ret *= a) %= mod;
            (a *= a) %= mod;
            b >>= 1;
        }
        return ret;
    }
    void init() {
        int tot = 0; mu[1] = 1;
        for (int i = 2; i <= maxn; ++i) {
            if (!check[i]) {
                prime[tot++] = i;
                mu[i] = -1;
            }
            for (int j = 0; j < tot; ++j) {
                if (i * prime[j] > maxn) break;
                check[i * prime[j]] = true;
                if (i % prime[j] == 0) {
                    mu[i * prime[j]] = 0;
                    break;
                }
                mu[i * prime[j]] = -mu[i];
            }
        }
        for (int i = 1; i <= maxn; ++i) mu[i] += mu[i - 1];
        inv = poww(3, mod - 2);
    }
    LL mu_sum(int x) {
        if (x <= maxn) return (LL)mu[x];
        if (sum.find(x) != sum.end()) return sum[x];
        int le, ri;
        LL ret = 0;
        for (int i = 2; i <= x; i = ri + 1) {
            le = i, ri = x / (x / i);
            ret = (ret + ((ri - le + 1) * mu_sum(x / i) + mod) % mod + mod) % mod;
        }
        return sum[x] = (1 + mod - ret) % mod;
    }
    LL pre(LL x) {
        return x * (x - 1) % mod * (x - 2) % mod * inv % mod;
    }
    void work() {
        LL n;
        scanf("%lld", &n);
        LL ans = 0, le, ri;
        for (LL i = 1; i <= n; i = ri + 1) {
            le = i, ri = n / (n / i);
            ans = (ans + (mu_sum(ri) - mu_sum(le - 1) + mod) % mod * pre(n / i) % mod + mod) % mod;
        }
        printf("%lld\n", ans);
    }
    int main() {
        init();
        int T;
        scanf("%d", &T);
        while (T--) work();
        return 0;
    }
    

    法二:杜教筛直接上+暴力预处理 811ms

    推导

    因为

    d|Nf(d)=f(N)+d|N,d<Nf(d)=N23N+2

    所以
    f(N)=N23N+2d|N,d<Nf(d)

    两边求和
    i=1Nf(i)=i=1N(i23i+2)i=1Nd|i,d<if(d)=i=1N(i23i+2)k=2Nd=1Nkf(d)

    G(N)=Ni=1f(i),上式即为
    G(N)=i=1N(i23i+2)k=2NG(Nk)

    杜教筛即可。

    其实后面这部分的推导都是套路=。=
    想了很久 1e7G() 该怎么线性筛无果…后来去搜了搜发现很多人都是直接暴力…暴力的话就到 1e6 吧…。
    真是一点都不优美啊

    Code

    #include <bits/stdc++.h>
    #define maxn 1000000
    #define maxm maxn + 10
    #include <map>
    using namespace std;
    typedef long long LL;
    const LL mod = 1e9+7;
    map<int, LL> sum;
    LL inv, g[maxm];
    LL poww(LL a, LL b) {
        LL ret = 1;
        while (b) {
            if (b & 1) (ret *= a) %= mod;
            (a *= a) %= mod;
            b >>= 1;
        }
        return ret;
    }
    void init() {
        for (int i = 1; i <= maxn; ++i) g[i] = (LL)(i - 1) * (i - 2) % mod;
        for (int i = 1; i <= maxn; ++i) {
            for (int j = i << 1; j <= maxn; j += i) {
                g[j] = (g[j] - g[i] + mod) % mod;
            }
        }
        for (int i = 1; i <= maxn; ++i) (g[i] += g[i - 1]) %= mod;
        inv = poww(3, mod - 2);
    }
    LL pre(LL x) {
        return x * (x - 1) % mod * (x - 2) % mod * inv % mod;
    }
    LL g_sum(int x) {
        if (x <= maxn) return g[x];
        if (sum.find(x) != sum.end()) return sum[x];
        int le, ri;
        LL ret = 0;
        for (int i = 2; i <= x; i = ri + 1) {
            le = i, ri = x / (x / i);
            ret = (ret + ((ri - le + 1) * g_sum(x / i) + mod) % mod + mod) % mod;
        }
        return sum[x] = (pre(x) - ret + mod) % mod;
    }
    void work() {
        LL n;
        scanf("%lld", &n);
        printf("%lld\n", g_sum(n));
    }
    int main() {
        init();
        int T;
        scanf("%d", &T);
        while (T--) work();
        return 0;
    }
    
    展开全文
  • 莫比乌斯反演 莫比乌斯反演基本形式: 对于一个函数f(x)f(x)f(x) 设g(x)=∑x∣df(d)g(x)=\sum _{x \mid d} f(d)g(x)=∑x∣d​f(d),那么 f(x)=∑x∣dμ(dx)⋅g(d)f(x)=\sum _{x \mid d} \mu(\frac {d} {x}) \cdot g...
  • 下面的blog讲的非常好,转! [莫比乌斯反演]https://www.cnblogs.com/peng-ym/p/8647856.html [杜教筛]https://www.cnblogs.com/peng-ym/p/9446555.html
  • 题解 数论劝退… 大佬博客 · 忘了再看呗 莫比乌斯函数 莫比乌斯反演 杜教筛
  • 这几天做了几道和杜教筛有关的题目,赶紧记下来怕以后忘了 首先就是最常用的式子 对于一个函数f(x) 设$g(x) =\sum_{x|d}f(d)$ 则根据莫比乌斯反演有$$f(x) = \sum_{x|d}μ(\frac{d}{x})g(d)$$ 举一个最常见...
  • 莫比乌斯反演 我们知道积性函数可以迪雷克卷积 我们知道F(x)=Σd|xf(d) 要求f(x) 两面卷上一个μ 得 F∗μ=f∗1∗μF∗μ=f∗1∗μF*μ=f*1*μ 得 F∗μ=f∗(1∗μ)F∗μ=f∗(1∗μ)F*μ=f*(1*μ) 得...
  • [复习]莫比乌斯反演,杜教筛,min_25 莫比乌斯反演 做题的时候的常用形式: \[\begin{aligned}g(n)&=\sum_{n|d}f(d)\\f(n)&=\sum_{n|d}\mu(\frac{d}{n})g(d)\end{aligned}\] 实际上还有 \[\begin{aligned}g...
  • 推导过程这篇博客一模一样,我就不再写一遍了,直接上答案。 这道题主要是考杜教筛
  • 题目的意思很简单,求给定区间内的gcd=k的个数,这应该是传统的莫比乌斯反演了。 有两种思路,一种是直接将里面变成gcd=1,然后里面看作元函数用莫比乌斯函数恒等函数展开,然后改变求和顺序。 还有一种是构造两个...
  • 狄利克雷卷积 狄利克雷卷积与数论函数构成群,四个性质: 封闭性 结合律 逆元 ...莫比乌斯反演 欧拉函数+莫比乌斯函数点这里 约数反演 定义: 反演: 证明:(狄利克雷卷积) ...
  • 莫比乌斯反演题改编,杜教筛中难题目,你会发现前面推了一页后终于才用到杜教筛
  • 考虑杜教筛,要求一个函数的前缀,可以考虑构造另一个函数,使得我们能求出另一个函数的前缀与两个函数狄利克雷卷积的前缀。 这里我们找到了$\varphi$  $\sum_{i=1}^n\varphi(i)\sum_{j=1}^{\lfloor \...
  • 题目分析 瞎推公式 让我们来乱推一波公式……首先我们要求: ...看到gcd,想到莫比乌斯反演,根据我们做莫比乌斯反演题的经验,枚举gcd的值,得到: ∑d=1nd∑i=1n∑j=1nij[gcd(i,j)==d]∑d=1nd∑i=1n∑j=...
  • 正题 ... 题目大意 给出nnn,求∑i=1n∑j=1nσ(i∗j)\sum_{i=1}^n\sum_{j=1}^...其中σ\sigmaσ表示约数。 解题思路 首先有结论σ(i∗j)=∑x∣i∑y∣j[gcd(x,y)==1]xyj\sigma(i*j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]\f
  • 狄利克雷卷积 性质 常见积性函数 常见积性函数证明 莫比乌斯反演 前置知识——整除分块 推公式 gcd的关系还有各种例题 各种例题 ...杜教筛 优秀blog bzoj 3944 sum 复杂度??? ...
  • 大致题意:自己看吧…… 直接上莫比乌斯反演。 令,显然g是一个积性函数,我们考虑用杜教筛求它的前缀。 ...
  • 用自己的想法AC后,发现时间比大部分代码快,直接到rank2,然后略微优化了一下线性预处理部分(理论上预处理到n的2/3次方也就是1e6最优,不过这题似乎2e6最优。) 这是我AC后找的某一个博主写的题解,里面的第一种...
  • BZOJ 3994 [SDOI2015]约数个数 BZOJ 4805 欧拉函数求和 BZOJ 2440 [中山市选2011]完全平方数 Luogu P3935 Calculating Luogu P4450 双亲数 BZOJ 4916 神犇蒟蒻 需要一点“小”技巧 BZOJ 2005 [Noi2010]能量采集 ...
  • 就是对于不能直接杜教筛的式子,可以将其与另一个前缀易求的积性函数狄利克雷卷积,使得卷积后的函数前缀和也易求。 比如这道题就是与 \(f(x)=x^2\) 卷积。 这道题也涉及到一些常见的化式子的方法。 \(\gcd\to...
  • 【BZOJ3930】选数(莫比乌斯反演杜教筛) 题面 给定\(n,K,L,R\) 问从\(L~R\)中选出\(n\)个数,使得他们\(gcd=K\)的方案数 题解 这样想,既然\(gcd=K\),首先就把区间缩小一下 这样变成了\(gcd=1\) 设\(f(i)\)表示...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,178
精华内容 471
关键字:

莫比乌斯反演和杜教筛