zcmimi's blog

arrow_back莫比乌斯共20篇文章

avatar
zc
2020-03-18 02:07:00
查看原题

点击跳转

前置知识:

  1. 杜教筛(包括狄利克雷卷积)

  2. 数论分块

  3. 欧拉函数 或 莫比乌斯函数

(会杜教筛的大佬上述都会吧)

欧拉函数卷积推导

\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j)

根据 \sum\limits_{i|n}\varphi(n)=n (1 * \varphi = Id)

= \sum_{i=1}^n\sum_{j=1}^n ij \sum_{k|i,k|j} \varphi(k)

调换枚举顺序

= \sum_{k=1}^n \varphi(k) \sum_{k|i,k|j} ij \\ = \sum_{k=1}^n \varphi(k) \sum_{k|i}i \sum_{k|j}j \\ = \sum_{k=1}^n \varphi(k) (\sum_{i=1}^{\left \lfloor\frac nk\right\rfloor}ki)^2 \\ = \sum_{k=1}^n \varphi(k) k^2(\sum_{i=1}^{\left \lfloor\frac nk\right\rfloor}i)^2

莫比乌斯函数推导

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

为了方便,设sum(T)=\sum_{i=1}^T i

=\sum_{d=1}^n d^3 \sum_{k=1}^{\left \lfloor\frac nd\right\rfloor}\mu(k)k^2sum(\left \lfloor \frac n{dk}\right \rfloor)^2

T=dk

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

其中: \sum_{d|T}d\mu(\frac Td)=\varphi(T)(\mu * Id = \varphi)

=\sum_{T=1}^n sum(\left \lfloor \frac nT\right \rfloor)^2 T^2 \varphi(T)

上述两种方法推导出的最终结果是一样的

接下来:

\sum_{k=1}^n \varphi(k)用杜教筛求出前缀和

k^2(\sum_{i=1}^{\left \lfloor\frac nk\right\rfloor}i)^2可以用数论分块求解

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

点击跳转

avatar
zc
2020-03-15 16:07:00
查看原题

点击跳转

f=\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=d] \\ f=\sum_{i=1}^{\left \lfloor \frac ad \right \rfloor} \sum_{j=1}^{\left \lfloor \frac bd \right \rfloor} [gcd(i,j)=1] \\ \because \sum_{x|n} \mu(x) = [n=1] \\ \therefore f= \sum_{i=1}^{\left \lfloor \frac ad \right \rfloor} \sum_{j=1}^{\left \lfloor \frac bd \right \rfloor} \sum_{k|gcd(i,j)} \mu(k) \\ f=\sum_{k=1}^{\left \lfloor \frac ad \right \rfloor}\mu(k)\left \lfloor \frac a{dk} \right \rfloor \left \lfloor \frac b{dk} \right \rfloor

avatar
zc
2020-03-15 16:05:00
查看原题

点击跳转

把题目强行转换为[POI2007]ZAP-Queries

Ans((1,b),(1,d))-Ans((1,b),(1,c-1))-Ans((1,a-1),(1,d))+Ans((1,a-1),(1,c-1))

f=\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=d] \\ f=\sum_{i=1}^{\left \lfloor \frac ad \right \rfloor} \sum_{j=1}^{\left \lfloor \frac bd \right \rfloor} [gcd(i,j)=1] \\ \because \sum_{x|n} \mu(x) = [n=1] \\ \therefore f= \sum_{i=1}^{\left \lfloor \frac ad \right \rfloor} \sum_{j=1}^{\left \lfloor \frac bd \right \rfloor} \sum_{k|gcd(i,j)} \mu(k) \\ f=\sum_{k=1}^{\left \lfloor \frac ad \right \rfloor}\mu(k)\left \lfloor \frac a{dk} \right \rfloor \left \lfloor \frac b{dk} \right \rfloor

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

点击跳转

n<m \prod_{i=1}^n \prod_{j=1}^m f_{\gcd(i,j)} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^n \sum_{j=1}^m[\gcd(i,j)=d]} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \sum_{j=1}^{\left \lfloor \frac md \right \rfloor}[\gcd(i,j)=1]} \\ =\prod_{d=1}^n{f_d}^{\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor} \mu(i) \left \lfloor \frac n{id}\right \rfloor \left \lfloor \frac m{id}\right \rfloor}

数论分块套数论分块会tle,继续老套路优化

T=id

=\prod_{T=1}^n\sum_{d|T}{f_d}^{\mu(\frac Td) \left \lfloor \frac n{T}\right \rfloor \left \lfloor \frac m{T}\right \rfloor}

可以先预处理出函数s(T)=\sum_{d|T}{f_d}^{\mu(\frac Td)}的前缀积

然后就可以做到数论分块O(\sqrt n)的复杂度了

avatar
zc
2020-03-14 20:35:00
查看原题

点击跳转

n<m,\sigma(d)d的约数和

先不考虑\sigma(\gcd(i,j))\le a

\sum_{i=1}^n\sum_{j=1}^m \sigma(\gcd(i,j)) \\ =\sum_{d=1}^n \sigma(d) \sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=d] \\ =\sum_{d=1}^n \sigma(d) \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac md \right \rfloor} [\gcd(i,j)=1] \\ =\sum_{d=1}^n \sigma(d) \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac md \right \rfloor} \sum_{x|i,x|j} \mu(x) \\ =\sum_{d=1}^n \sigma(d) \sum_{x=1}^{\left \lfloor \frac nd \right \rfloor} \mu(x) {\left \lfloor \frac n{dx} \right \rfloor}{\left \lfloor \frac m{dx} \right \rfloor}

T=dx

=\sum_{T=1}^n {\left \lfloor \frac nT \right \rfloor}{\left \lfloor \frac mT \right \rfloor}\sum_{d|T}\sigma(d) \mu(\left \lfloor \frac Td \right \rfloor)

考虑a的限制

g(T)=\sum_{d|T}\sigma(d) \mu(\left \lfloor \frac Td \right \rfloor)

可以发现当d\ge a的时候才会产生贡献

将询问按a排序

每次询问的时候,按倍数枚举找到所有新的可以产生贡献的T,

动态修改g(T),可以选择树状数组这种又短常数又小的好东西

avatar
zc
2020-03-14 03:42:00
查看原题

点击跳转

求: \sum_{i=1}^n\sum_{j=1}^mlcm(i,j)

n<m \sum_{i=1}^n\sum_{j=1}^mlcm(i,j) \\ =\sum_{i=1}^n\sum_{j=1}^m \frac{ij}{\gcd(i,j)} \\ =\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m \frac {ij}d[\gcd(i,j)=d]

i'=\left \lfloor \frac id \right \rfloor,j'=\left \lfloor \frac jd \right \rfloor

\\ =\sum_{d=1}^n\sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac md \right \rfloor} ijd[\gcd(i,j)=1]

\sum\limits_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum\limits_{j=1}^{\left \lfloor \frac md \right \rfloor} ij[\gcd(i,j)=1]拆出来,

sum(n,m)=

\sum_{i=1}^n\sum_{j=1}^n ij[\gcd(i,j)=1] \\ =\sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)} ij\mu(d) \\ =\sum_{d=1}^n\sum_{d|i}\sum_{d|j} ij\mu(d)

i'=\left \lfloor \frac id \right \rfloor,j'=\left \lfloor \frac jd \right \rfloor

=\sum_{d=1}^n\mu(d)d^2\sum_{i=1}^{\left \lfloor \frac nd\right \rfloor}\sum_{j=1}^{\left \lfloor \frac md\right \rfloor} ij

g(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^mij

g(n,m)=\frac{n(n+1)}2\cdot \frac{m(n+1)}2

最后

ans=\sum_{d=1}^n d\cdot sum(\left\lfloor \frac nd \right\rfloor,\left\lfloor \frac md \right\rfloor) \\ sum(n,m)=\sum_{d=1}^n\mu(d)d^2 g(\left\lfloor \frac nd \right\rfloor,\left\lfloor \frac md \right\rfloor)

avatar
zc
2020-03-12 23:16:00
查看原题

点击跳转

题意:求第k个没有完全平方数因子的数

可以发现答案具有单调性,可以二分答案,然后判断[1,n]中满足条件的个数是否为k

这个结果为

1(0个平方因子)的倍数-【4,9,16,25,...】(1个平方因子)的倍数+【36,100,...】(2个平方因子)的倍数...

也就是:

\sum_{i=1}^{i^2\le n} \mu(i)\left \lfloor \frac n{i^2}\right \rfloor

这样的话只需要线性筛到\sqrt{10^9}\le 40000,然后二分查找就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

\sum_{x=1}^n \sum_{y=1}^n [gcd(x,y)=1][a_{b_x}=b_{a_y}]

可以直接记录v[a_{b_x}]然后统计,用莫比乌斯容斥

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

前置定理:

d(ij) = \sum_{x|i} \sum_{y|j}[gcd(x,y) = 1]

所以:

n<m

\sum_{i=1}^n \sum_{j=1}^m d(ij) \\ =\sum_{i=1}^n \sum_{j=1}^m \sum_{x|i} \sum_{y|j}[gcd(x,y) = 1] \\ =\sum\limits_{x=1}^n\sum\limits_{y=1}^m \left\lfloor\frac{n}{x}\right\rfloor \left\lfloor\frac{m}{y}\right\rfloor [\gcd(x,y)=1]

x、y换成i、j

\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor[\gcd(i,j)=1] \\ =\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor \sum_{k|gcd(i,j)}\mu(k)

g(i)=\sum_{i=1}^n \left \lfloor \frac ni \right \rfloor

ans=\sum_{k=1}^n\mu(k) g(\left \lfloor \frac nk \right \rfloor) g(\left \lfloor \frac mk \right \rfloor) \\

2/2
Search
search