\[\sum_{i=1}^n\sum_{j=1}^n\frac{i+j}{\gcd(i,j)}
\]
先化式子：
\[\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^n\frac{i+j}{\gcd(i,j)}&=
\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n\frac{i+j}{d}[\gcd(i,j)=d]\\&=
\sum_{d=1}^n\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}(i+j)[\gcd(i,j)=1]\\&=
\sum_{d=1}^n\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}(i+j)\sum_{x=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(x)[x|i][x|j]\\&=
\sum_{d=1}^n\sum_{x=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(x)x\sum_{i=1}^{\left\lfloor\frac{n}{xd}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{xd}\right\rfloor}(i+j)
\end{aligned}\]
有一个性质：
\[\sum_{i=1}^n\sum_{j=1}^n(i+j)=n^2(n+1)
\]
故上式可化为：
\[\sum_{d=1}^n\sum_{x=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(x)x\left\lfloor\frac{n}{xd}\right\rfloor^2(\left\lfloor\frac{n}{xd}\right\rfloor+1)
\]
套路的设 \(T=xd\)，有：
\[\sum_{T=1}^n\sum_{d|T}\mu(d)d\left\lfloor\frac{n}{T}\right\rfloor^2(\left\lfloor\frac{n}{T}\right\rfloor+1)
\]
设 \(f(n)=\sum\limits_{d|n}\mu(d)d\)，我们发现一个神奇的性质：\(f*\varphi=\epsilon\)，即 \(f\) 是 \(\varphi\) 的逆元，那么 \(f\) 就容易用杜教筛筛出，再套上一层整除分块，时间复杂度为 \(O(n^{\frac{2}{3}})\)。
\[\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\max(a_i,a_j,a_k)
\]
首先可以发现将 \(a\) 以任意顺序排列均不影响所求值，那么我们不妨先将 \(a\) 从小到大排序。
我们观察在 \(i\) 固定时随着 \(j\) 的变化所产生的贡献总和，容易发现，当 \(i,j\) 固定时，由 \(k\) 产生贡献为 \(\max(i,j)\max(a_i,a_j)+\sum_{k=\max(i,j)+1}^n a_k\)，再考察一下 \(j\) 的变化，可以得到：
\[\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\max(a_i,a_j,a_k)=\sum_{i=1}^n(i\times(ia_i+\sum_{j=i+1}^na_j)+\sum_{j=i+1}^nja_j+\sum_{j=i+1}^n\sum_{k=j+1}^na_k)
\]
这个式子可以通过预处理 \(\sum_{i=1}^n a_i\)，\(\sum_{i=1}^n i\times a_i\) 和 \(\sum _{i=x}^n\sum_{j=i+1}^n a_j\) 做到线性统计答案。
这样我们就可以 \(O(n\log n)\) 做完了。
首先想到 bitset，我们对于每个集合开一个 bitset，询问时只需要将两个 bitset 与一下就可以了。
但这样空间复杂度会炸掉，因此我们考虑根号分治平衡时空复杂度，具体的说，我们设定一个阈值 \(B\)，只对 \(|S|>B\) 的集合 \(S\) 开 bitset，查询时将小于 \(B\) 的集合放入一个公用的 bitset 中再与另一个 bitset 与，再把公用的 bitset 清空。
这样的时间复杂度为 \(O(\frac{mq}{w}+qB)\)，空间复杂度为 \(O(\frac{m^2}{B})\)，时空都可以接受。