题目所求即
\[\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)} \]这里没有出现\([gcd(x,y)=1]\)，所以我们枚举\(gcd\)的值来硬凑，原式就等于
\[\sum_{d=1}^{min(n,m)}\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)}[gcd(i,j)=d] \]为了出现\([gcd(i,j)=1]\)，直接将\(i,j\)变成\(d\)的倍数，原式就等于
\[\sum_{d=1}^{min(n,m)}\sum_{d|i}\sum_{d|j}\frac{ij}{d}[gcd(i,j)=d]=\sum_{d=1}^{min(n,m)}\sum_{k=1}^{\frac{n}{d}}\sum_{t=1}^{\frac{m}{d}}ktd[gcd(k,t)=1]=\sum_{d=1}^{min(n,m)}d\sum_{k=1}^{\frac{n}{d}}\sum_{t=1}^{\frac{m}{d}}kt\sum_{p|gcd(k,t)}u(p)=\sum_{d=1}^{min(n,m)}d\sum_{p=1}^{min(\frac{n}{d},\frac{m}{d})}u(p)\sum_{p|k}\sum_{p|t}kt=\sum_{d=1}^{min(n,m)}d\sum_{p=1}^{min(\frac{n}{d},\frac{m}{d})}u(p)\sum_{i=1}^{\frac{n}{dp}}ip\sum_{j=1}^{\frac{m}{dp}}jp=\sum_{d=1}^{min(n,m)}d\sum_{p=1}^{min(\frac{n}{d},\frac{m}{d})}u(p)p^2(\sum_{i=1}^{\frac{n}{dp}}i)(\sum_{j=1}^{\frac{m}{dp}}j) \]最后两项用等差数列求和公式就好了，然后分块套分块即可
标签：frac,gcd,min,sum,JZPTAB,ij,Crash,国家集训队,dp From： https://www.cnblogs.com/dingxingdi/p/18175963