bzoj3994【莫比乌斯函数】

最关键的是这个恒等式

然后推式子就行了

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef long long LL;
inline int read()
{
	int x=0;bool f=0;char c=getchar();
	for (;c<'0'||c>'9';c=getchar()) f=c=='-'?1:0;
	for (;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
	return f?-x:x;
}
const int N=50010;
int pr[N],pc=0,mu[N],ma[N];
bool np[N];LL d[N];

int main()
{
	mu[1]=1;d[1]=1;ma[1]=0;
	for (int i=2;i<N;i++)
	{
		if (!np[i]) pr[++pc]=i,mu[i]=-1,d[i]=2,ma[i]=1;
		for (int j=1,k=i<<1;j<=pc&&k<N;k=i*pr[++j])
		{
			np[k]=1;
			if (i%pr[j]==0) 
			{
				mu[k]=0;ma[k]=ma[i]+1;
				d[k]=d[i]/(ma[i]+1)*(ma[k]+1);
				break;
			}
			mu[k]=-mu[i];ma[k]=1;
			d[k]=d[i]<<1;
		}
	}
	for (int i=1;i<N;i++) d[i]+=d[i-1],mu[i]+=mu[i-1];
	for (int cas=read(),A,B,n,ans;cas--;)
	{
		A=read();B=read();n=min(A,B);LL ans=0;
		for (int i=1,pos,dA,dB;i<=n;i=pos+1)
		{
			dA=A/i;dB=B/i;
			pos=min(A/dA,B/dB);
			ans+=(mu[pos]-mu[i-1])*d[dA]*d[dB];
		}
		printf("%lld\n",ans);
	}
	return 0;
}