前置芝士
关于这个题，你必须知道一个这样奇奇怪怪的式子啊QAQ
\[d(i*j)= \sum_{x|i} \sum_{y|j}[gcd(x,y)=1] \]
留坑，先感性理解：后面那个gcd是为了去重。
UPD：
-------- 正文
根据前一部分，我们所要推倒的式子就变成了
\[ans=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}\left [ gcd(x,y)=1 \right ]\]
我们可以改变一下枚举顺序，原来是枚举原数，现在我们改为枚举约数，再利用数学性质将其倍数全部筛掉，式子即变成
\[ans=\sum_{i=1}^{n}\sum_{j=1}^{m}\left \lfloor \frac{n}{i} \right \rfloor\left \lfloor \frac{m}{j} \right \rfloor\left [ gcd(i,j)=1 \right ]\]
于是，我们可以把里面的那个东西稍稍的替换一下
\[ans=\sum_{i=1}^{n}\sum_{j=1}^{m}\left \lfloor \frac{n}{i} \right \rfloor\left \lfloor \frac{m}{j} \right \rfloor\sum_{d|gcd(i,j)}\mu (d)\]
根据莫比乌斯函数的性质，这两个东西显然是等价的。
然后我们可以在和式枚举时就将gcd消掉,同时将d调整到和式最外层
然后整个式子就变成
\[ans=\sum_{d=1}^{min(n,m)}\mu (d)\sum_{x=1}^{\left \lfloor \frac{n}{x} \right \rfloor}\left \lfloor \frac{n}{dx} \right \rfloor\sum_{y=1}^{\left \lfloor \frac{m}{y} \right \rfloor}\left \lfloor \frac{m}{dy} \right \rfloor\]
唯一的难点是，$\sum_{x=1}^{\left \lfloor \frac{n}{x} \right \rfloor}\left \lfloor \frac{n}{dx} \right \rfloor $
将\(n/x\)，换成一个变量，就会发现，这东西也是可以分块的！！！
然后就可以愉快的整除分块了
贴代码
#include#include #include using namespace std;typedef long long ll;const int maxn=5e4+10;int miu[maxn],prime[maxn],t;bool vis[maxn];ll g[maxn];void get_g(){ for(int i=1;i<=maxn;++i) { int l,r; for(l=1;l<=i;l=r+1) { r=i/(i/l); g[i]+=(i/l)*(r-l+1); } }}//同样分块处理 void mobius(){ miu[1]=1; for(int i=2;i<=maxn;i++) { if(vis[i]==0) miu[i]=-1,++t,prime[t]=i; for(int j=1;j<=t&&i*prime[j]<=maxn;++j) { vis[i*prime[j]]=1; if(!(i%prime[j])) break; else miu[i*prime[j]]-=miu[i]; } } for(int i=1;i<=maxn;++i) miu[i]+=miu[i-1];}int main(){ get_g(); mobius(); int t; int n,m; scanf("%d",&t); for(int _=1;_<=t;++_) { ll ans=0; scanf("%d%d",&n,&m); int tmp=min(n,m); long long l,r; for(l=1;l<=tmp;l=r+1) { r=min(n/(n/l),m/(m/l)); ans+=(miu[r]-miu[l-1])*g[n/l]*g[m/l]; } printf("%lld\n",ans); }}