WELCOME——一只蒟蒻的幻想
点击这里去虐题
题意要求$\sum_{i=a}^{b}\sum_{j=c}^{d}e(gcd(i,j)=k)$
首先我们可以利用容斥，将二维区间的询问改为四个二维前缀的询问。
然后显然的$\sum_{i=1}^{n}\sum_{j=1}^{m}e(gcd(i,j)=k)=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}e(gcd(i,j))$
然后尝试化简
$$
\begin{align}
& \ \sum_{i=1}^{n}\sum_{j=1}^{m}e(gcd(i,j)) \\
= & \ \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d) \\
= & \ \sum_{d}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\mu(d) \\
= & \ \sum_{d}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \\
\end{align}
$$
对于$\lfloor\frac{n}{d}\rfloor$的值，只有$\sqrt{n}$种，预处理莫比乌斯函数前缀和之后分段处理。
点击这里去虐题
题意要求
$$
\begin{align}
& \ \sum_{i=1}^{n}\sum_{j=1}^{m}(gcd(i,j)*2-1) \\
= & \ 2*\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)-n*m \\
\end{align}
$$
然后就如同上题一样求出$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)$即可
点击这里去虐题
题意要求$\sum_{i=1}^{n}\sum_{j=1}^{m}1(gcd(i,j)是质数)$
我们设$f(n)=
\begin{cases}
1\ \ \ n是质数 \\
0\ \ \ n不是质数 \\
\end{cases}
$
于是问题就变成了求$\sum_{i=1}^{n}\sum_{j=1}^{m}f(gcd(i,j))$了
$$
\begin{align}
& \ \sum_{i=1}^{n}\sum_{j=1}^{m}f(gcd(i,j)) \\
= & \ \sum_{d}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}f(d)e(gcd(i,j)) \\
= & \ \sum_{d}f(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{d’|gcd(i,j)}\mu(d’) \\
= & \ \sum_{d}\sum_{d’}f(d)\mu(d’)\sum_{i=1}^{\lfloor\frac{n}{dd’}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dd’}\rfloor} \\
= & \ \sum_{d}\sum_{d’}f(d)\mu(d’)\lfloor\frac{n}{dd’}\rfloor\lfloor\frac{m}{dd’}\rfloor \\
\end{align}
$$
设$g(n)=\sum_{d|n}f(d)\mu(\frac{n}{d})$
$$
\begin{align}
& \ \sum_{d}\sum_{d’}f(d)\mu(d’)\lfloor\frac{n}{dd’}\rfloor\lfloor\frac{m}{dd’}\rfloor \\
= & \ \sum_{i=1}^{n}g(i)\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor \\
\end{align}
$$
然后与上题类似预处理g的前缀和，对函数分段计算。
点击这里去虐题
将上题中的函数f的定义换一下就可以。
点击这里去虐题
题意要求$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$
尝试转化成枚举Gcd的形式
$$
\begin{align}
& \ \sum_{i=1}^{n}\sum_{j=1}^{m}\left(\frac{i*j}{gcd(i,j)}\right) \\
= & \ \sum_{d}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\left(\frac{id*jd}{d}\right)e(gcd(i,j)) \\
= & \ \sum_{d}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i*j\sum_{d’|gcd(i,j)}\mu(d’) \\
= & \ \sum_{d}\sum_{d’}d*d’^2*\mu(d’)\sum_{i=1}^{\lfloor\frac{n}{dd’}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dd’}\rfloor}i*j \\
\end{align}
$$
很显然的可以得到$\sum_{i=1}^{n}\sum_{j=1}^{m}i*j=\frac{1}{4}nm(n+1)(m+1)$
与上题类似地设$g(n)=\sum_{d|n}d^2*\mu(d)*\frac{n}{d}$
$$
\begin{align}
& \ \sum_{d}\sum_{d’}d*d’^2*\mu(d’)\sum_{i=1}^{\lfloor\frac{n}{dd’}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dd’}\rfloor}i*j \\
= & \ \sum_{i}g(i)\sum_{i=1}^{\lfloor\frac{n}{i}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{i}\rfloor}i*j
\end{align}
$$
因为g是积性函数，所以可以做到$O(n)$预处理。
点击这里去虐题
与上题相同，多组数据
点击这里去虐题
题意要求$\sum_{i_1|a_1}\sum_{i_2|a_2}\cdots\sum_{i_n|a_n}\varphi(i_{1}i_{2}\cdots i_n)$
我们知道$\varphi$是一个积性函数，考虑通过积性函数的性质进行计算
考虑分解质因子计算，求出每一种质因子的$\varphi$值即可，先计算出所有的组合情况
设$q_i$为$p$因子在$a_i$中出现的次数，那么就是要求$$sum=\prod_{i=1}^{n}\sum_{k=0}^{q_i}p_i$$
只有不含$p$因子的那一项不乘$\frac{p-1}{p}$，单独处理即可，易得对答案的贡献为$$\frac{p-1}{p}(sum-1)+1$$
当$a_i$较大的时候需要使用rho等高效的分解质因数方法。
点击这里去虐题
题意要求$$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)^{gcd(i,j)}$$
考虑改为枚举gcd的形式
$$
\begin{align}
& \ \sum_{i=1}^{n}\sum_{j=1}^{m}(\frac{i*j}{gcd(i,j)})^{gcd(i,j)} \\
= & \ \sum_{d}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}(\frac{id*jd}{d})^{d}e(gcd(i,j)) \\
= & \ \sum_{d}d^{d}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}(i*j)^{d}\sum_{d’|gcd(i,j)}\mu(d’) \\
= & \ \sum_{d}d^{d}\sum_{d’}\mu(d’)\sum_{i=1}^{\lfloor\frac{n}{dd’}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dd’}\rfloor}(id’*jd’)^{d} \\
= & \ \sum_{d}d^{d}\sum_{d’}\mu(d’)d’^{2d’}\sum_{i=1}^{\lfloor\frac{n}{dd’}\rfloor}i^d\sum_{j=1}^{\lfloor\frac{m}{dd’}\rfloor}j^d \\
\end{align}
$$
对于每一个$d$暴力维护一下$\sum_{d’}\mu(d’)d’^{2d’}$和$\sum_{i=1}^{\lfloor\frac{n}{dd’}\rfloor}i^d$即可
点击这里去虐题
题意要求$$\sum_{i=1}^{n}\sum_{j=1}^{i}\mu(lcm(i,j)^{gcd(i,j)})$$
有错误请指出$$Continue…$$