题目大意

设d(x)为x的约数个数，\(t\)组询问，给定\(n,m\)(\(t,m,n\leq5*10^4\))，求$ \sum^n_{i=1}\summ_{j=1}d(i*j)$

题解

假设\(n\leq m\)

设\(i=p_1^{a_1}*p_2^{a_2}*...*p_k^{a_k},j=p_1^{b_1}*p_2^{b_2}*...*p_k^{b_k}\)

对于\(i*j\)的某个约数\(x\)，设\(x=p_1^{c_1}*p_2^{c_2}*...*p_k^{c_k}\)，那么可以用两个数\(e,f\)表示\(x\)，当\(c_q\leq a_q\)时\(e\)的\(p_q\)的指数为\(c_q\)，当\(c_q> a_q\)时\(f\)的\(p_q\)的指数为\(c_q-a_q\)

这样每个\(x\)都能对应到一对\((e,f)\)上，每对满足\(e|i,f|j,gcd(e,f)=1\)的\((e,f)\)也能对应到一个\(x\)上

所以就有\(d(i,j)=\sum_{e|i}\sum_{f|j}[gcd(e,f)=1]\)

原式=$ \sum^n_{i=1}\summ_{j=1}\sum_{e|i}\sum_{f|j}[gcd(e,f)=1]\(
把枚举\)e,f\(放到前面，得原式=\)\sum_{e=1}^{{n}\sum_{f=1}}{m}\lfloor\frac{n}{e}\rfloor\lfloor\frac{m}{f}\rfloor[gcd(e,f)=1]\(
=\)\sum_{e=1}^{{n}\sum_{f=1}}{m}\lfloor\frac{n}{e}\rfloor\lfloor\frac{m}{f}\rfloor\sum_{i|e,i|f}\mu(i)\(
=\)\sum_{i=1}^{{n}\mu(i)\sum_{i|e}}{n}{\lfloor\frac{n}{e}\rfloor}\sum_{i|f}^{m}{\lfloor\frac{m}{f}\rfloor}\(
=\)\sum_{i=1}^{{n}\mu(i)\sum_{e=1}}{\lfloor\frac{n}{i}\rfloor}{\lfloor\frac{n}{ei}\rfloor}\sum_{f=1}^{\lfloor\frac{m}{i}\rfloor}{\lfloor\frac{m}{fi}\rfloor}\(
设\)g(x)=\sum_{i=1}^{x}{\lfloor\frac{x}{i}\rfloor}\(，预处理\)g(x)\(
则原式=\)\sum_{i=1}^{n}{\mu(i)g(n/i)g(m/i)}$

接下来整除分块就行了

代码

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define maxn 50010

#define lim 50000

#define LL long long

using namespace std;

int read()

{

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)&&ch!='-')ch=getchar();

	if(ch=='-')f=-1,ch=getchar();

	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return x*f;

}

void write(LL x)

{

	if(x==0){putchar('0'),putchar('\n');return;}

	int f=0;char ch[20];

	if(x<0)putchar('-'),x=-x;

	while(x)ch[++f]=x%10+'0',x/=10;

	while(f)putchar(ch[f--]);

	putchar('\n');

	return;

}

int n,m,t,p[maxn],no[maxn],cnt;

LL f[maxn],g[maxn],mu[maxn];

int main()

{

	//freopen(".in","r",stdin);

	//freopen(".out","w",stdout);

	mu[1]=p[1]=no[1]=1;

	rep(i,2,lim)

	{

		if(!no[i])p[++cnt]=i,mu[i]=-1;

		for(int j=1;j<=cnt&&i*p[j]<=lim;j++)

		{

			no[i*p[j]]=1;

			if(i%p[j]==0){mu[i*p[j]]=0;break;}

			else mu[i*p[j]]=-mu[i];

		}

	}

	rep(i,1,lim)mu[i]+=mu[i-1];

	rep(i,1,lim)

	{

		for(int l=1,r=0;l<=i;l=r+1)

		{

			r=i/(i/l);

			f[i]+=(LL)(i/l)*(LL)(r-l+1);

		}

	}

	t=read();

	while(t--)

	{

		n=read(),m=read();LL ans=0;

		if(n>m)swap(n,m);

		for(int l=1,r=0;l<=n;l=r+1)

		{

			r=min(n/(n/l),m/(m/l));

			ans+=(mu[r]-mu[l-1])*f[n/l]*f[m/l];

		}

		write(ans);

	}

	return 0;

}