zcmimi's blog

arrow_back莫比乌斯共20篇文章

avatar
zcmimi
2020-06-09 16:22:00

DZY Loves Math

题意:

对于正整数n,定义f(n)n所含质因子的最大幂指数

例如f(1960)=f(2^3\cdot 5^1\cdot 7^2)=3,f(10007)=1,f(1)=0

给定正整数a,b,求$\sum\limits_{i=1}^a\s

avatar
zcmimi
2020-03-12 20:40:00

该好好复习(总结)一下莫比乌斯函数了呢\mathcal{>_\omega<}

定义

$$ \mu (i)= \begin{cases} 1,i=1 \ (-1)^k,i=p_1\times p_2\times \dots \times p_k \ 0,rest \end{cases

avatar
zc
2020-08-08 20:19:00
查看原题

点击跳转

\begin{aligned} &\quad\sum_{i=1}^n \gcd(i,n)^x lcm(i,n)^y \\ &=\sum_{i=1}^n \frac{in}{lcm(i,n)}^x lcm(i,n)^y \\ &=\sum_{i=1}^n (in)^x lcm(i,n)^{y-x} \\ &=\sum_{i=1}^n (in)^x \frac{in}{\gcd(i,n)}^{y-x}\\ &=\sum_{i=1}^n (in)^y \gcd(i,n)^{x-y} \\ &=n^y\sum_{d|n} d^{x-y}\sum_{i=1}^n i^y [\gcd(i,n)=d] \\ &=n^y\sum_{d|n} d^{x-y}\sum_{i=1}^{n/d} (id)^y [\gcd(i,n)=1] \\ &=n^y\sum_{d|n} d^{x-y}\sum_{i=1}^{n/d} (id)^y \sum_{k|i,k|n}\mu(k) \\ &=n^y\sum_{d|n} d^{x-y}\sum_{k|\frac nd}\mu(k)\sum_{i=1}^{n/dk} (idk)^y \\ &=n^y\sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^y\sum_{i=1}^{n/dk} i^y \end{aligned}

\displaystyle S_k(n)=\sum_{i=1}^{n-1}i^k,可以看做一个y+1次多项式,假设求出后每一项系数为t_i

=n^y\sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^yS_y(\frac n{dk}) \\ =n^y\sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^y\sum_{i=0}^{y+1}t_i(\frac n{dk})^i \\ =n^y\sum_{i=0}^{y+1}t_i \sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^y (\frac n{dk})^i

其中,设\displaystyle Z(n)=\sum_{d|n} d^x\sum_{k|\frac nd}\mu(k)k^y (\frac n{dk})^i ,

可以看成f(d)=d^x,g(d)=\mu(d)d^y,h^i(d)=d^i这三个积性函数的狄利克雷卷积

卷积后还是积性函数,且狄利克雷卷积满足交换律,只有当x=1x=p^k\mu(x)\ne 0

\begin{cases} Z(1)=1\\ Z(p)=p^x-p^y+p^i\\ Z(p^k)=(f * h^i)(p^k)-(f * h^i)(p^{k-1}) \cdot p^y \end{cases}

其中\displaystyle (f * h^i)(p^k)=\sum_{i+j=k} f(p^i)\cdot h^i(p^j)

使用Pollard-Rhon分解质因数,枚举每个质因子(包括次幂),然后狄利克雷卷积计算答案

avatar
zc
2020-06-11 16:49:00
查看原题

点击跳转

f_i表示所有数\gcdi还要加入的数的期望数量

ans=1+\frac{\sum_{i=1}^mf_i}m

可以知道f_1=0

f_i=1+\frac{\sum_{j=1}^m f_{\gcd(i,j)}}m(i>1)

继续推式子:

\begin{aligned} f_i &=1+\frac{\sum_{j=1}^m f_{\gcd(i,j)}}m\\ &=1+\frac{\sum_{d|i} f_d\sum_{j=1}^m [\gcd(i,j)=d]}m \end{aligned}

把分子拿出来

\begin{aligned} &\quad\sum_{d|i} f_d\sum_{j=1}^m [\gcd(i,j)=d]\\ &=\sum_{d|i} f_d\sum_{j=1}^{m/d} [\gcd(\frac id,j)=1]\\ &=\sum_{d|i} f_d\sum_{j=1}^{m/d} \sum_{x|\frac id,x|j}\mu(x)\\ &=\sum_{d|i} f_d \sum_{x|\frac id}\sum_{j=1}^{m/dx}\mu(x)\\ &=\sum_{d|i} f_d \sum_{x|\frac id}\mu(x)\left \lfloor \frac m{dx}\right\rfloor\\ \end{aligned}\\

T=dx

=\sum_{T|i}\sum_{d|T} f_d \mu(\frac Td)\left \lfloor \frac mT\right\rfloor

带入原来的式子

f_i=1+\frac{\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)}m

F_T=\sum_{d|T} f_d \mu(\frac Td)

d\not = i时可以每算出一个f_i就更新所有F_x(i|x)

d=i时没法直接更新,这时T=d=i,\mu(\frac Td)=\mu(1)=1

f_i=1+\frac{\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m+\frac{f_i\left\lfloor \frac mi \right\rfloor}m \\ f_i-\frac{f_i\left\lfloor \frac mi \right\rfloor}m=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m \\ f_i\frac{m-\left\lfloor\frac mi \right\rfloor}m=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}m \\ f_i=\frac{m+\sum_{T|i}\left \lfloor \frac mT\right\rfloor\sum_{d|T} f_d \mu(\frac Td)[d\not=i]}{m-\left\lfloor\frac mi \right\rfloor}

这样就可以先算f_i,再算F_i

[d\not=i]这个条件只在T=i的时候才有限制

枚举到T=i,计算f_i时,F_x(x<i)都已经计算好了

F_i还少了f[i] \times \mu(1)

这正好是要剪掉的部分

avatar
zc
2020-06-09 16:10:00
查看原题

点击跳转

a_i=\sum\limits_{j=1}^N[A_j=i],n=10^6

\sum_{i=1}^n\sum_{j=i+1}^n \operatorname{lcm}(A_i,A_j)\\ =\sum_{i=1}^n\sum_{j=i+1}^n a_ia_j\frac{ij}{\gcd(i,j)}\\ =\sum_{d=1}^n\frac 1d\sum_{i=1}^n\sum_{j=i+1}^n a_ia_j ij [\gcd(i,j)=d]\\ =\sum_{d=1}^n\frac 1d\sum_{i=1}^{n/d}\sum_{j=i+1}^{n/d} a_{id}a_{jd} idjd [\gcd(i,j)=1]\\ =\sum_{d=1}^n d \sum_{i=1}^{n/d}\sum_{j=i+1}^{n/d} a_{id}a_{jd} ij [\gcd(i,j)=1]\\ =\sum_{d=1}^n d \sum_{i=1}^{n/d}\sum_{j=i+1}^{n/d} a_{id}a_{jd} ij \sum_{x|i,x|j}\mu(x)\\ =\sum_{d=1}^n d \sum_{x=1}^n\mu(x)\sum_{i=1}^{n/dx}\sum_{j=i+1}^{n/dx} a_{idx}a_{jdx} ixjx\\ =\sum_{d=1}^n d \sum_{x=1}^n\mu(x)x^2 \sum_{i=1}^{n/dx}\sum_{j=i+1}^{n/dx} a_{idx}a_{jdx} ij\\ T=dx =\sum_{T=1}^n T \sum_{x|T}\mu(x)x \sum_{i=1}^{n/T}\sum_{j=i+1}^{n/T} a_{iT}a_{jT} ij

avatar
zc
2020-03-20 12:57:00
查看原题

点击跳转

带 套 路 题

\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\mu^2(\gcd(i,j))\gcd(i,j) \\ =\sum_{d=1}^n \mu^2(d) d \sum_{i=1}^n\sum_{j=1}^n(i+j)^k[\gcd(i,j)=d] \\ =\sum_{d=1}^n \mu^2(d) d^{k+1} \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac nd \right \rfloor}(i+j)^k[\gcd(i,j)=1]

S(n)=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k

=\sum_{d=1}^n \mu^2(d) d^{k+1} \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac nd \right \rfloor}(i+j)^k \sum_{x|i,x|j} \mu(x) \\ =\sum_{d=1}^n \sum_{x=1}^{\left \lfloor \frac nd \right \rfloor}\mu^2(d) d^{k+1} \mu(x) x^k S(\left \lfloor \frac n{dx} \right \rfloor)

T=dx

=\sum_{T=1}^n \sum_{d|T} \mu^2(d) d^{k+1} \mu(\frac Td) (\frac Td)^k S(\left \lfloor \frac nT \right \rfloor) \\ =\sum_{T=1}^n S(\left \lfloor \frac nT \right \rfloor) T^k \sum_{d|T} d \mu^2(d)\mu(\frac Td)

如何快速求令S(n)?

设:

F(n)=\sum_{i=1}^n i^k

G(n)=\sum_{i=1}^n F(i)

那么

S(n)=\sum_{i=n+1}^{2n}F(i)-\sum_{i=1}^nF(i) \\ =G(2n)-2G(n)

筛出F的前缀和,然后筛S(n)

优化:

因为模数是质数,根据欧拉定理: 对于互质的a,n满足a^{\varphi(n)} \equiv 1\pmod n

可以k=k \mod 998244352

求后半部分

f(n)=\sum_{d|n} d \mu^2(d)\mu(\frac nd)

如何线性求f(n)?

f(n)是若干个积性函数的卷积,所以f(n)也是积性函数

那么f(n)=f(p^k)f(\frac n{p^k})

f(1)=1

f(p^1)=p-1(带入即可得到)

f(p^2)=-p(带入即可得到)

f(p^k)=0(k\ge 3)

d\frac nd中必然有一个有平方因子,所以\mu(d)\mu(\frac nd)必有一项为0

所以f(p^k)=0(k\ge 3)

接下来就可以线性筛f(n)

avatar
zc
2020-03-19 23:44:00
查看原题

点击跳转

经过一番化简后变成了:

\sum_{i=1}^{\sqrt{2n}} \sum_{x=L}^{R} [\gcd(i,x)=1] \\ L=Max(1,i-\lfloor {n\over i}\rfloor) \\ R=Min(i-1,\lfloor {n\over i }\rfloor)

莫比乌斯反演

\sum_{i=1}^{\sqrt{2n}} \sum_{j=l}^{R} [\gcd(i,j)=1] \\ =\sum_{i=1}^{\sqrt{2n}} \sum_{j=l}^{R} \sum_{k|i,k|j} \mu(k) \\ =\sum_{i=1}^{\sqrt{2n}}\sum_{k|j,k\in[L,R]} \mu(k)

avatar
zc
2020-03-19 20:28:00
查看原题

点击跳转

\sum_{i=1}^A\sum_{j=1}^B [\gcd(i,j)=d] \\ =\sum_{i=1}^{\left \lfloor \frac Ad \right \rfloor}\sum_{j=1}^{\left \lfloor \frac Bd\right \rfloor} [\gcd(i,j)=1] \\ =\sum_{i=1}^{\left \lfloor \frac Ad \right \rfloor}\sum_{j=1}^{\left \lfloor \frac Bd\right \rfloor} \sum_{x|i,x|j}\mu(x) \\ =\sum_{x=1}^n\mu(x) \left \lfloor \frac A{dx} \right \rfloor \left \lfloor \frac B{dx}\right \rfloor

avatar
zc
2020-03-19 17:10:00
查看原题

点击跳转

首先L=\left \lceil \frac LK\right \rceil,H=\left \lceil \frac HK\right \rceil

问题转化为在[L,H]中取 N\gcd=1的数 的方案数

f_i为选出 N个不完全相同\gcd=i的数 的方案数

x[L,R]i的倍数的个数,x=\sum_{j=L}^H [i|j]=\left \lfloor \frac Hi \right \rfloor-\left \lfloor \frac Li \right \rfloor

暂时令f_i=x^N-x(所有减去完全相同的)

这时候f_i实际上是选出 N个不完全相同i|\gcd的数 的方案数

假设我们已经知道了f_{2i},f_{3i},...的最终结果

那么把f_i减去f_{2i},f_{3i},...就可以了

avatar
zc
2020-03-19 15:44:00
查看原题

点击跳转

\sum_{i=1}^n\sum_{j=1}^n lcm(A_i,A_j)

a_i = \sum_{j=1}^n [A_j=i]

那么

ans = \sum_i^n \sum_j^n a_ia_j \frac{ij}{\gcd(i,j)} \\ = \sum_{d=1}^n \frac 1d \sum_{i=1}^n \sum_{j=1}^n a_ia_j ij[\gcd(i,j)=d] \\ = \sum_{d=1}^n \sum_{i=1}^{\frac nd} \sum_{j=1}^{\frac nd}d \times a_{id}a_{jd}ij[\gcd(i,j)=1] \\ \text{唉,到这里我就不会了} \\ =\sum_{p=1}^np\sum_{i=1}^{n/p}\sum_{j=1}^{n/p}a_{ip}a_{jp}ij\sum_{d|i,d|j}\mu(d) \\ =\sum_{p=1}^np\sum_{d=1}^n\mu(d)d^2\sum_{i=1}^{n/dp}\sum_{j=1}^{n/dp}a_{idp}a_{jdp}ij \\ =\sum_{q=1}^nq\sum_{d|q}d\mu(d)\sum_{i=1}^{n/q}\sum_{j=1}^{n/q}a_{iq}a_{jq}ij \\ =\sum_{q=1}^nq\sum_{d|q}d\mu(d)\left(\sum_{i=1}^{n/q}a_{iq}i\right)^2

1/2
Search
search