\(\sum_{i=1}^N \sum_{j=1}^M [(i,j)=1]\)
\(f(d)=\sum_{i=1}^N \sum_{j=1}^M [(i,j)=d]\)
\(g(d)=\sum_{i=1}^N \sum_{i=1}^M [d|(i,j)]=\lfloor \frac{N}{d} \rfloor \lfloor \frac{M}{d} \rfloor\)
\(g(n)=\sum_{n|d} f(d)\)
\(f(n)=\sum_{n|d} \mu(\frac{d}{n})g(d)\)
\(f(1)=\sum_{i=1}^{\min(N,M)} \mu(i)\lfloor \frac{N}{i} \rfloor \lfloor \frac{M}{i} \rfloor\)
\(\sum_{i=1}^N \sum_{j=1}^M (i,j)\)
\(f(d)=\sum_{i=1}^N \sum_{j=1}^M d[(i,j)=d]=d\sum_{i=1}^N \sum_{j=1}^M [(i,j)=d]=d\sum_{i=1}^{\lfloor \frac{\min(N,M)}{d} \rfloor} \mu(i) \lfloor \frac{N}{id} \rfloor \lfloor \frac{M}{id} \rfloor\)
\(Ans=\sum_{d=1}^{\min(N,M)} f(d)=\sum_{d=1}^{\min(N,M)} d\sum_{i=1}^{\lfloor \frac{\min(N,M)}{d} \rfloor} \mu(i) \lfloor \frac{N}{id} \rfloor \lfloor \frac{M}{id} \rfloor\)
设\(w=id\)
\(Ans=\sum_{w=1}^{\min(N,M)} \sum_{d|w} \mu(\frac{w}{d}) \lfloor \frac{N}{w} \rfloor \lfloor \frac{M}{w} \rfloor=\sum_{w=1}^{\min(N,M)} \lfloor \frac{N}{w} \rfloor \lfloor \frac{M}{w} \rfloor \sum_{d|w} \mu(d)\)
\(\sum_{d|w} \mu(d)\)显然是积性函数，线性筛后做下前缀和，离线\(\Theta(\max(N,M))\)
\(\sum_{w=1}^{\min(N,M)} \lfloor \frac{N}{w} \rfloor \lfloor \frac{M}{w} \rfloor\) 整除分块可以做到在线\(\Theta(\sqrt{N}+\sqrt{M})\)
多组询问下总复杂度\(\Theta(\max(N,M)+T(\sqrt{N}+\sqrt{M}))\)
\(\sum_{i=1}^N \sum_{j=1}^M \frac{ij}{(i,j)}\)
\(f(d)=\sum_{i=1}^{\lfloor \frac{N}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{M}{d} \rfloor} ijd[(i,j)=1]=d \sum_{i=1}^{\lfloor \frac{N}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{M}{d} \rfloor} ij[(i,j)=1]\)
\(Ans=\sum_{d=1}^{\min(N,M)} f(d)\)
\(Ans=\sum_{d=1}^{\min(N,M)} d \sum_{i=1}^{\lfloor \frac{N}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{M}{d} \rfloor} ij\sum_{n|(i,j)} \mu(n)\)
\(Ans=\sum_{d=1}^{\min(N,M)} d \sum_{n=1}^{\lfloor \frac{\min(N,M)}{d} \rfloor} n (\sum_{i=1}^{\lfloor \frac{N}{dn} \rfloor} i)n(\sum_{j=1}^{\lfloor \frac{M}{dn} \rfloor} j)\)
设\(w=dn\)
\(Ans=\sum_{w=1}^{\min(N,M)} (\sum_{i=1}^{\lfloor \frac{N}{w} \rfloor} i)(\sum_{j=1}^{\lfloor \frac{M}{w} \rfloor} j) w\sum_{n|w} n \mu(n)\)
线筛前缀和+整除分块
复杂度与上题相同
原文：https://www.cnblogs.com/AH2002/p/10029079.html