正解:莫比乌斯反演
解题报告:
先考虑证明一个结论,$d_{i\cdot j}=\sum_{p|i}\sum_{q|j}[gcd(p,q)==1]$
看起来就很对的样子,但还是证下趴$QwQ$
考虑分解质因数,设$i=p_{1}^{a_{1}}\cdot p_{2}^{a_{2}}\cdot p_{3}^{a_{3}},j=p_{1}^{b_{1}}\cdot p_{2}^{b_{2}}\cdot p_{3}^{b_{3}}$,则$i\cdot j=p_{1}^{a_{1}+b_{1}}\cdot p_{2}^{a_{2}+b_{2}}\cdot p_{3}^{a_{3}+b_{3}}$,则有$d_{i\cdot j}=\prod (a_{i}+b_{i}+1)$
于是记$p_{i}$的贡献为$(a_{i}+b_{i}+1)$,考虑结论右侧的一对取值,设$t1,t2$互质且都不含质因数$p_{i}$,则$(t_{1}\cdot p_{i}^{a_{i}},b_{i}),(t_{1}\cdot p_{i}^{a_{i}-1},b_{i}),...,(t_{1},b_{1}\cdot p_{i}^{b_{i}})$都会有1的贡献,总共就是$a_{i}+b_{i}+1$的贡献,得证!
欧克证完结论就要考虑公式变形了鸭$QwQ$
$\sum_{i=1}^{n}\sum_{j=1}^{m}d_{i\cdot j}=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{p|i}\sum_{q|j}[gcd(p,q)==1]$
考虑每一个数对$t_{1},t_{2}$会被枚举多少次?显然$t_{1}$会被枚举$\frac{n}{t_{1}}$次,$t_{2}$会被枚举$\frac{m}{t_{2}}$次
于是继续变形得,原式=$\sum_{t_{1}=1}^{n}\sum_{t_{2}=1}^{m}\frac{n}{t_{1}}\cdot \frac{m}{t_{2}}\cdot [gcd(t_{1},t_{2})==1]$
这时候考虑到莫比乌斯函数的性质,$\left\{\begin{matrix}\sum_{d|n}\mu(d)=0,n>1\\ \sum_{d|n}\mu(d)=1,n=1\end{matrix}\right.$,于是原式可以化为,$\sum_{t_{1}=1}^{n}\sum_{t_{2}=1}^{m}\frac{n}{t_{1}}\cdot \frac{m}{t_{2}}\cdot \sum_{d|gcd(t_{1},t_{2})}\mu(d)=\sum_{t_{1}=1}^{n}\sum_{t_{2}=1}^{m}\frac{n}{t_{1}}\cdot \frac{m}{t_{2}}\cdot \sum_{d|t_{1}\text{&}d|t_{2}}\mu(d)$
然后按照一般的套路来说这里就差不多要考虑变换下$\sum$的顺序了
这儿就考虑把$\sum mu(d)$提到最前面,不难想到式子就变成了,$\sum \mu(d)\cdot \sum_{t_{1}=1}^{\frac{n}{d}}\sum_{t_{2}=1}^{\frac{m}{d}}\frac{n}{t_{1}\cdot d}\cdot \frac{m}{t_{2}\cdot d}$
嗷这样儿还不够,最后还要再,变下形$QwQ$,$\sum_{d=1}^{min(m,n)} \mu(d)\cdot \sum_{t_{1}=1}^{\frac{n}{d}}\frac{n}{t_{1}\cdot d}\cdot \sum_{t_{2}=1}^{\frac{m}{d}}\frac{m}{t_{2}\cdot d}$,发现对于$\sum_{t_{1}=1}^{\frac{n}{d}}\frac{n}{t_{1}\cdot d}$这样儿一个式子,其实$\frac{n}{d}$是固定的,设$x=\frac{n}{d}$,于是原式变为$\sum_{t_{1}=1}^{d}\frac{d}{i}$
考虑预处理一个$g(d)=\sum_{t_{1}=1}^{d}\frac{d}{i}$,于是答案式变为$\sum_{d=1}^{min(m,n)} \mu(d)\cdot g(\frac{n}{d})\cdot g(\frac{m}{d})$
然后到这儿依然没有结束昂嘤嘤嘤,,,
考虑$g(d)$怎么预处理鸭$QAQ$
显然直接暴力地$O(n^{2})$处理是不可取的$QwQ$
于是考虑这个所谓$g(d)$的意义是啥昂$QwQ$
观察$g(d)$的表达式,不难发现$g(x)$可以理解为$\sum_{i=1}^{x}$$x$范围内为$i$的倍数的数的数量之和,也就是题目中的$d(x)$的前缀和,于是现在就变成了线性求$d(x)$
我的方法是直接枚举质因数,然后用类似埃氏筛的方法,对质因数的倍数直接乘指数+1即可$QwQ$
然后还有就是,莫比乌斯反演的话,数论分块是基本素养了趴,,,?太套路了不说了$QwQ$
$over$
啊记得开$ll$鸭
真·$over$
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define il inline
#define int long long
#define fi first
#define sc second
#define gc getchar()
#define mp make_pair
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i) const int N=5e4+;
int g[N],sum[N],pr[N],pr_cnt,miu[N];
bool is_prim[N]; il int read()
{
ri x=;rb y=;rc ch=gc;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il void pre_g()
{
rp(i,,N-)g[i]=;sum[]=;
rp(i,,N-)
{
if(!is_prim[i])g[i]=g[i]<<;sum[i]=sum[i-]+g[i];
if(!is_prim[i]){rp(j,,(N-)/i){ri tmp=,tmp_j=j;while(j%i==)++tmp,j/=i;j=tmp_j;g[i*j]*=(tmp+);}}
}
}
il void pre_mu()
{
miu[]=;
rp(i,,N-)
{
if(!is_prim[i])miu[i]=-,pr[++pr_cnt]=i;
rp(j,,pr_cnt){if(pr[j]*i>N-)break;is_prim[pr[j]*i]=;if(!(i%pr[j])){miu[i*pr[j]]=;break;}else miu[i*pr[j]]=-miu[i];}
}
rp(i,,N-)miu[i]+=miu[i-];
} main()
{
freopen("3327.in","r",stdin);freopen("3327.out","w",stdout);
pre_mu();pre_g();ri T=read();
while(T--)
{ri n=read(),m=read(),ret=,j;if(n>m)swap(n,m);for(ri i=;i<=n;i=j+){j=min(n/(n/i),m/(m/i));ret+=(miu[j]-miu[i-])*sum[n/i]*sum[m/i];}printf("%lld\n",ret);}
return ;
}