标签为 [莫比乌斯反演] 的文章

BZOJ3994 约数个数和

题目大意 设d(x)为x的约数个数。有多组询问,每次给定N、M,求$ \sum_{i=1}^{N}\sum_{i=1}^{m}d(i,j)$ Solution 有一个式子:$ d(n,m)=\sum_{i|n}\sum_{j|m}\varepsilon(gcd(i,j))$。可以自己证明一下。 设n<m,然后就可以转化式子了。$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{u|i}\sum_{v|j}\varepsilon(gcd(u,v))$$ $$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{u|i}\sum_{v|j}\sum_{(d|u)\land(d|v)}\mu(d)$$ $$=\sum_{d=1}^{n}\mu(d)\sum_{u=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{v=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{d ......

BZOJ2301 Problem b

题目大意 对于给出的n个询问,每次求$ \sum_{i=a}^{b}\sum_{j=c}^{d}[\gcd(i,j)==k]$。 Solution 如果令f(n,m)=$ \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)==k]$, 则最后的答案ans=f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,b-1)。所以只要求f(n,m)。 令$ n1=\lfloor\frac{n}{k}\rfloor$,$ m1=\lfloor\frac{m}{k}\rfloor$;且设n<=m $$f(n,m)=\sum_{i=1}^{n1}\sum_{j=1}^{m1}\varepsilon(gcd(i,j))$$ $$=\sum_{i=1}^{n1}\sum_{j=1}^{m1}\mu(gcd(i,j))*\mathrm{1}$$ $$=\sum_{i=1}^{n1}\sum_{j=1}^{m1}\sum_{(d|i)\land(d|j)}\mu(d)$$ $$=\s ......

BZOJ 3561 DZY Loves Math VI

题目传送门 Solution 很明显是莫比乌斯反演啦 令p=gcd(i,j),且n<m $$=\sum_{i=1}^{n}\sum_{j=1}^{m}{(\frac{i}{p})}^p{(\frac{j}{p})}^{p}{p}^{p}$$ $$=\sum_{p=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}{(ijp)}^p\cdot\varepsilon(gcd(i,j))$$ $$=\sum_{p=1}^{n}p^p\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}{(ij)}^p\cdot\mu(gcd(i,j))\ast\mathrm{1}$$ $$=\sum_{p=1}^{n}p^p\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\fra ......

BZOJ2818GCD

题目传送门 这是一道非常简单的莫比乌斯反演题 $$\sum_{d\in p}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\varepsilon(gcd(i,j))$$ $$=\sum_{d\in p}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}(\mu*1)(gcd(i,j))$$ $$=\sum_{d\in p}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{k|i,k|j}\mu(k)$$ $$=\sum_{d\in p}\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{n}{dk}\r ......