各种数学求和

记录遇到的数学求和乱七八糟题

1 2019江西邀请赛B

$$\prod^{n}_{i=1}\prod^{n}_{j=1}\prod^{n}_{d=1}m^{gcd(i,j)^{[d|gcd(i,j)]}}(n\leq1e9)$$

设$x=gcd(i,j)$

$$\sum^{n}_{x=1}{}\sum^{n}_{i=1}\sum^{n}_{j=1}xd(x)*[gcd(i,j)==x]$$ $$\sum^{n}_{x=1}{xd(x)}\sum^{\frac{n}{x}}_{i=1}\sum^{\frac{n}{x}}_{j=1}[gcd(i,j)==1]$$ $$\sum^{n}_{x=1}{xd(x)}(2*\sum^{\frac{n}{x}}_{i=1}{\phi(x)}-1)$$

2 P3172 [CQOI2015]选数

$$\sum_{i_{1}=L}^{R}\sum_{i_{2}=L}^{R}\sum_{i_{3}=L}^{R} ...\sum_{i_{n}=L}^{R}[gcd(i_{1},i_{2},i_{3}..i_{n})=k]$$

莫比乌斯反演

$$\sum_{i_{1}=\frac{L-1}{k}+1}^{\frac{R}{k}}\sum_{i_{2}=\frac{L-1}{k}+1}^{\frac{R}{k}}\sum_{i_{3}=\frac{L-1}{k}+1}^{\frac{R}{k}} ...\sum_{i_{n}=\frac{L-1}{k}+1}^{\frac{R}{k}}[gcd(i_{1},i_{2},i_{3}..i_{n})=1]$$

$r=\frac{R}{k}$
$l=\frac{L-1}{k}+1$

$$\sum_{d=1}^{r}\mu(d)\sum_{i_{1}=\frac{l-1}{d}+1}^{\frac{r}{d}}\sum_{i_{2}=\frac{l-1}{d}+1}^{\frac{r}{d}}\sum_{i_{3}=\frac{l-1}{d}+1}^{\frac{r}{d}} ...\sum_{i_{n}=\frac{l-1}{d}+1}^{\frac{r}{d}}1$$

即从$[\frac{l-1}{d}+1,\frac{r}{d}]选n个数对$$(r-l+1)^n$

$$\sum_{d=1}^{r}\mu(d)(\frac{r}{d}-\frac{l-1}{d})^n$$

3 HDU6715

$$\sum_{i=1}^{n}\sum_{j=1}^{m} \mu(lcm(i,j)) \ (n,m\leq 10^6)\\$$

$
证： \mu(lcm(i,j))=\mu(i)\times\mu(j)\times\mu(gcd(i,j))
$

$
\because i|lcm(i,j),
j|lcm(i,j),
gcd(i,j)|lcm(i,j)
$

$
\therefore \mu(i)=0\ or\ \mu(j)=0 \ or\ \mu(gcd(i,j))=0
$

$
\therefore \mu(lcm(i,j)) = 0
$

当都不为0的时候
$
\because K=k_{i}+{k_{j}}-{k_{gcd(i,j)}},
\mu(k)=(-1)^k
$

$$\therefore \mu(lcm(i,j))=\mu(i)*\mu(j)*\mu(gcd(i,j))\\$$

开始化简

$$\sum_{i=1}^{n}\sum_{j=1}^{m} \mu(i)*\mu(j)*\mu(gcd(i,j))\\ \sum_{k=1}^{R}\mu(k)\sum_{i=1}^{n}\sum_{j=1}^{m} \mu(i)*\mu(j)[gcd(i,j)=k]\\ \sum_{k=1}^{R}\mu(k)\sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{m}{k}} \mu(ki)*\mu(kj)[gcd(i,j)=1]\\ \sum_{k=1}^{R}\mu(k)\sum_{d=1}^{\frac{R}{k}}\mu(d)\sum_{i=1}^{\frac{n}{dk}}\sum_{j=1}^{\frac{m}{dk}} \mu(dki)*\mu(dkj)$$

令$dk=T$

$$\sum_{T=1}^{R}\sum_{i=1}^{\frac{n}{T}}\mu(Ti)\sum_{j=1}^{\frac{m}{T}} \mu(Tj)\sum_{d|T}\mu(d)\mu(\frac{T}{d})$$

根据$(1+\frac{1}{2}+\frac{1}{3}….\frac{1}{n})*n=nlog(n)$
所以只需要预处理前三项，就好了

4 BZOJ 4659

$$f(T)=\sum_{d|T}d\mu(d)*\mu^2(\frac{T}{d})$$

显然为积性函数，可通过线性筛推出。

$$f(p)=1-p, f(p^2)=p*\mu(p)*\mu^2(p)=-p, f(p^3)=0$$

注意:本题$mod=2^{30}$，而$unsigned$系列自然溢出$2^{32}$和$2^{64}$,所以计算时只需要最后$\% 2^{32}$

5 2019 银川 D

$$\sum_{i_{1}=1}^{m}\sum_{i_{2}=1}^{m}\sum_{i_{3}=1}^{m} ...\sum_{i_{n}=1}^{m}(i_1*i_2...i_n)^k[gcd(i_{1},i_{2},i_{3}..i_{n})=d](n\leq 10^{100000},m,k,d\leq 10^5)\\ \sum_{i_{1}=1}^{\frac{m}{d}}\sum_{i_{2}=1}^{\frac{m}{d}}\sum_{i_{3}=1}^{\frac{m}{d}} ...\sum_{i_{n}=1}^{\frac{m}{d}}(d*i_1*d*i_2...d*i_n)^k[gcd(i_{1},i_{2},i_{3}..i_{n})=1]\\ P3768一样莫比乌斯反演\\ d^{nk}\sum_{i_{1}=1}^{\frac{m}{d}}\sum_{i_{2}=1}^{\frac{m}{d}}\sum_{i_{3}=1}^{\frac{m}{d}} ...\sum_{i_{n}=1}^{\frac{m}{d}}(i_1*i_2...i_n)^k\sum_{x|gcd(i_{1},i_{2},i_{3}..i_{n})}\mu(x)\\ d^{nk}\sum_{x=1}^{\frac{m}{d}}\mu(x)\sum_{i_{1}=1}^{\frac{m}{xd}}\sum_{i_{2}=1}^{\frac{m}{xd}}\sum_{i_{3}=1}^{\frac{m}{xd}} ...\sum_{i_{n}=1}^{\frac{m}{xd}}(x*i_1*x*i_2...x*i_n)^k\\ d^{nk}\sum_{x=1}^{\frac{m}{d}}\mu(x) x^{nk}\sum_{i_{1}=1}^{\frac{m}{xd}}\sum_{i_{2}=1}^{\frac{m}{xd}}\sum_{i_{3}=1}^{\frac{m}{xd}} ...\sum_{i_{n}=1}^{\frac{m}{xd}}(i_1*i_2...i_n)^k= d^{nk}\sum_{x=1}^{\frac{m}{d}}\mu(x) x^{nk}(\sum_{i=1}^{\frac{m}{xd}}(i)^k)^n\\$$

简单预处理一下，复习欧拉降幂

$$a^b = \begin{cases} a^{b\% \phi(p)} & gcd(a,p)=1 \\ a^{b} & gcd(a,p)!=1,b\leq\phi(p) \\ a^{b\% \phi(p)+\phi(p)} & gcd(a,p)!=1,b>\phi(p)\\ \end{cases}$$

6