[SDOI2015]约数个数和

题目链接：Click here

Solution:

首先，我们转化式子

\[\sum_{i=1}^n\sum_{j=1}^m d(ij)\\ \sum_{i=1}^n\sum_{j=1}^m \sum_{x|i} \sum_{y|j}[gcd(x,y)=1]\\ \]

我们把\(x,y\)给提前

\[\sum_{x=1}^n\sum_{y=1}^m \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y} \rfloor [gcd(x,y)=1] \]

我们把\(gcd(x,y)\)提前，\(x,y\)不太好看，再给他换个名字\(i,j\)

\[\sum_{i=1}^n \sum_{j=1}^m \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor \sum_{d|i} \sum_{d|j} \mu(d)\\ \]

我们把\(d\)提前

\[\sum_{d=1}^n \mu(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{n}{di} \rfloor \lfloor \frac{m}{dj} \rfloor \]

我们设一个函数\(g(n)=\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor\)，则有

\[\sum_{d=1}^n \mu(d) g(\lfloor \frac{n}{d} \rfloor) g(\lfloor \frac{m}{d} \rfloor) \]

这个数论分块即可，考虑怎么筛\(g(n)\)，我们可以发现\(g(n)=\sum_{i=1}^n d(i)\)，则我们筛\(d\)后做前缀和即可

Code:

#include
#define int long long
using namespace std;
const int N=5e4+11;
int n,m,u[N],p[N],vis[N];
int ans,cnt,g[N],num[N];
int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void prepare(){
    u[1]=1;g[1]=1;
    for(int i=2;i