\(P2261\)
显然，原式\(=\sum_{i=1}^n(k-\lfloor k/i\rfloor i)\)，数论分块即可。
\(P2260\)
不妨\(n\ge m\)。可以先求\(\sum_{i=1}^nn\space mod\space i\sum_{j=1}^mm\space mod\space j=\sum_{i=1}^n(n-\lfloor n/i\rfloor i)\sum_{j=1}^m(m-\lfloor m/j\rfloor j)\)，再减去\(\sum_{i=1}^m(n\space mod\space i)(m\space mod\space i)=\sum_{i=1}^m(nm-n\lfloor m/i\rfloor i-m\lfloor n/i\rfloor i+\lfloor n/i\rfloor \lfloor m/i\rfloor i^2)\)。其它的都好说，\(\lfloor n/i\rfloor \lfloor m/i\rfloor i^2\)项就直接同时数论分块，每次的\(r\)就是\(n\)的\(r\)和\(m\)的\(r\)取个\(min\)就行了。
\(P3455\)
转化为\(1\le x\le n=a/d,1\le y\le m=b/d,gcd(x,y)=1\)的\((x,y)\)数量。运用容斥，\(=\sum_d\mu(d)\lfloor n/d\rfloor\lfloor m/d\rfloor\)。预处理\(\mu\)及其前缀和，询问使用数论分块即可，复杂度\(O(n+T\sqrt n)\)。
\(CF547C\)
设数集为\(S\)。则运用容斥，答案为\(\sum_d\mu(d)\binom{num_d}{2}\)，其中\(num_i\)表示\(S\)中\(i\)倍数的个数。于是，我们维护关于\(d\)的每一项\(val_d\)和\(num_d\)，我们就可以快速进行单词修改。用调和级数预处理每个数的因数，复杂度\(O(VlnV+n+q\omega(V)))\)。
\(CF803F\)
在狄利克雷前缀和的复杂度内求出\(a\)序列中\(d\)倍数的个数\(num_d\)，那么运用容斥，答案为\(\sum_d\mu(d)(2^{num_d}-1)\)。预处理\(2\)的幂，复杂度\(O(VloglogV+n)\)。
\(CF900D\)
首先\(x|y\)，问题变为\(gcd=1\)且和为\(n=y/x\)的方案数。于是，运用容斥，答案为\(\sum_{d|n}\mu(d)f(n/d)\)，其中\(f(n)\)表示和为\(n\)，项数任意的正整数序列个数。显然，\(f(n)=\sum_{i=1}^n\binom{n-1}{i-1}=2^{n-1}\)。复杂度\(O(\sqrt nlogn)\)。
\(CF1559E\)
首先运用容斥，稍稍处理一下上下界，就变成了一个序列中每个数有上下界，和有上界，求序列个数的问题。这显然可以通过\(dp\)加前缀和优化在\(O(nm/d)\)的复杂度内解决问题，其中\(d\)为容斥的\(d\)。套上外面的容斥，复杂度\(O(nmlnm)\)。
\(P2257\)
设\(f(n)=[n\in prime],g=f*\mu\)，那么运用莫反，原式\(=\sum_dg(d)\lfloor n/d\rfloor\lfloor m/d\rfloor\)。若能快速预处理\(g\)，则可以运用数论分块，在\(T\sqrt n\)的时间内解决问题。
重点就是\(g\)的预处理。首先我们只需要枚举质数\(p\)及其倍数来更新就行，复杂度\(O(nloglogn)\)。但这不够优美，优美一点应该在线性筛时就求出\(g\)，因为\(g\)虽不是积性函数，但它的性质良好。我们对于质数直接求，对于\(i\space mod\space prime_j=0\)的只看\(f_{prime_j}\)的贡献，对于\(i\space mod\space prime_j\ne 0\)的将\(g_i\)取反再加上\(prime_j\)的贡献即可。这样复杂度\(O(n)\)，总共\(O(n+T\sqrt n)\)。
\(ATarc185e\)
预处理好\(2\)的幂。对于\(m\)，答案为\(\sum_{1\le i\le j\le m}gcd(a_i,a_j)2^{m-j+i-1}=2^{m-1}\sum_{1\le i\le j\le m}gcd(a_i,a_j)2^{i-j}=2^{m-1}\sum_d\varphi(d)\sum_{1\le i\le j\le m,d|a_i,d|a_j}2^{i-j}\)。我们抛开\(2^{m-1}\)，后面的维护每一项的值\(val_d\)以及为\(d\)倍数的位置的\(2^i\)之和\(sum_d\)。这样，调和级数预处理好每个数的因数，复杂度\(O(VlnV+n\omega(V))\)。
\(LOJ6375\)
这题直接上套路就\(T\)飞了，我们得反套路。我们发现\(gcd(n-i,n)=gcd(i,n)\)，所以我们首尾配对(注意边界)，原式\(=\frac{1}{2}(\sum_{i=1}^n\frac{n^2}{gcd(i,n)}+n)=\frac{n}{2}(\sum_{i=1}^n\frac{n}{gcd(i,n)}+1)=\frac{n}{2}(\sum_{d|n}d\varphi(d)+1)\)。容易发现\(h(n)=\sum_{d|n}d\varphi(d)\)是积性函数，可以线性筛，复杂度\(O(n+T)\)。
\(ATagc038c\)
设\(f(n)=1/n,g=f*\mu,h(n)=g(n)*n^2\)原式\(=\sum_{1\le i\le j\le n}\frac{a_ia_j}{gcd(a_i,a_j)}=\sum_dh(d)\sum_{1\le i\le j\le n,d|a_i,d|a_j}\frac{a_ia_j}{d^2}\)。可以用狄利克雷前缀和的复杂度求出\(i\)倍数的数的和及平方和，统计是简单的，复杂度\(O(VloglogV+n)\)。
\(P3704\)
我们做的一般是\(\sum\)的题，这次变成\(\prod\)了？所以我们要照葫芦画瓢，定义一下新运算了。
定义\(f\oplus g=h\)表示\(h(n)=\prod_{d|n}f(d)^{g(n/d)}\)。显然，\(f\oplus\epsilon=f\)，\((f\oplus g)\oplus h=f\oplus(g*h)\)。所以，如果\(f=g\oplus 1\)，那么两边同时\(\oplus\)上\(\mu\)，即可得到\(g=f\oplus \mu\)。我们就得到了莫反的形式了。
首先\(f_i(1\le i\le n)\)没有一个是\(0\)，这是一个十分重要的前提，否则后面的毫无意义。那么定义\(g=f\oplus\mu\)，原式\(=\prod_{i=1}^n\prod_{j=1}^mf_{gcd(i,j)}=\prod_dg(d)^{\lfloor n/d\rfloor\lfloor m/d\rfloor}\)。预处理好\(g\)的前缀积，使用数论分块+快速幂，就可以做到单次查询\(O(\sqrt nlogn)\)。
问题是，怎样是\(g\)的正确预处理方式？首先\(f\)及其逆元是可以且必须\(O(n)\)预处理的。然后有人就会\(O(nlnn)\)用调和级数直接求了，这是愚昧的。我们要用狄利克雷前缀和在\(O(nloglogn)\)内求，做一个它的反操作即可，这样就连\(\mu\)都不用求。但涉及除法，会加一个\(logp\)，怎么办？同时维护它的倒数即可。复杂度\(O(nloglogn+T\sqrt n)\)。
\(P3327\)
首先我们要注意到\(d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\)。我们对于每个\(p\)，设某因数\(d\)内有\(c\)个\(p\)，\(i\)内有\(a\)个\(p\)，\(j\)内有\(b\)个\(p\)。如果\(c\le a\)，那就往\(x\)上贡献\(c\)个\(p\)，否则就往\(y\)上贡献\(c-a\)个\(p\)，这样就能建立起一一对应了。
那么，原式\(=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]=\sum_d\mu(d)\sum_{d|x|i}\sum_{d|y|j}1=\sum_d\mu(d)s(n/d)s(m/d)\)，其中\(s\)为\(d(n)\)的前缀和。那么，预处理\(\mu\)的前缀和以及\(s\)，查询用数论分块，复杂度\(O(n+T\sqrt n)\)。