题意
\(T\) 组询问，每次询问求：
\[\sum_{i=1}^{n}\sum_{i=1}^{m} [\gcd(i,j) \in prime] \]\(T=10^4,n,m \leq 10^7\)。
思路
不难想到枚举质数，将原式化简为：
\[\sum_{p \in prime}\sum_{i=1}^{n}\sum_{i=1}^{m} [\gcd(i,j)= p] \]按照套路，提出后面的 \(p\)，得到：
\[\sum_{p \in prime}\sum_{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor }\sum_{i=1}^{\left \lfloor \frac{m}{p} \right \rfloor } [\gcd(i,j)= 1] \]套用莫比乌斯函数，得到：
\[\sum_{p \in prime}\sum_{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor }\sum_{i=1}^{\left \lfloor \frac{m}{p} \right \rfloor } \sum_{d|\gcd(i,j)} \mu(d) \]将莫比乌斯函数提到最前面去，得到：
\[\sum_{d=1} \mu(d) \sum_{p \in prime}\sum_{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor }\sum_{i=1}^{\left \lfloor \frac{m}{p} \right \rfloor } [d|i][d|j] \]后面的 \(d|i\) 其实就是在枚举 \(1 \sim \left \lfloor \frac{n}{p} \right \rfloor\) 中 \(d\) 的倍数有多少个，那么其实就是 \(\left \lfloor \frac{n}{pd} \right \rfloor\)，带入原式，得到：
\[\sum_{d=1} \mu(d) \sum_{p \in prime} \left \lfloor \frac{n}{pd} \right \rfloor \left \lfloor \frac{m}{pd} \right \rfloor \]到目前为止，利用数论分块，单次询问的复杂度为 \(O(质数的个数 \times \sqrt{n})\)。考虑进一步优化，设 \(k=pd\)，带入原式：
\[\sum_{p \in prime} \sum_{d=1} \mu(d) \left \lfloor \frac{n}{k} \right \rfloor \left \lfloor \frac{m}{k} \right \rfloor \]枚举一下 \(k\)，提到式子的前方，得到：
\[\sum_{k=1} \left \lfloor \frac{n}{k} \right \rfloor \left \lfloor \frac{m}{k} \right \rfloor \sum_{p|k,p \in prime} \mu(\frac{k}{p}) \]发现后面那个式子可以预处理掉，于是复杂度就为 \(O(T\sqrt{n})\)。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e7+10;
#define LL long long
int f[N],mu[N],n,prime[N],tot;bool vis[N];LL sum[N];
void init()
{
mu[1]=1;
for(int i=2;i<N;i++)
{
if(!vis[i]) prime[++tot]=i,mu[i]=-1;
for(int j=1;j<=tot&&prime[j]*i<N;j++)
{
vis[prime[j]*i]=true;
if(i%prime[j]==0) {mu[prime[j]*i]=0;break;}
mu[prime[j]*i]=-mu[i];
}
}
for(int i=1;i<=tot;i++) for(int j=prime[i];j<N;j+=prime[i]) sum[j]+=mu[j/prime[i]];
for(int i=2;i<N;i++) sum[i]+=sum[i-1];
}
LL solve(int n,int m)
{
LL res=0;
for(int l=1,r=0;l<=min(n,m);l=r+1)
{
r=min(n/(n/l),m/(m/l));
res+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);
}
return res;
}
int main()
{
init();int n,m,T;scanf("%d",&T);while(T--) scanf("%d%d",&n,&m),printf("%lld\n",solve(n,m));
return 0;
}