BZOJ_3994_[SDOI2015]约数个数和_莫比乌斯反演

BZOJ_3994_[SDOI2015]约数个数和_莫比乌斯反演

Description

 设d(x)为x的约数个数，给定N、M，求  

Input

输入文件包含多组测试数据。

第一行，一个整数T，表示测试数据的组数。

接下来的T行，每行两个整数N、M。

Output

T行，每行一个整数，表示你所求的答案。

Sample Input

2
7 4
5 6

Sample Output

110
121

HINT

1<=N, M<=50000

1<=T<=50000

---

基本同BZOJ4176，需要处理$f_n=\sum\limits_{i=1}n/i$，然后分块求。

 

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

typedef long long ll;

#define N 50050

using namespace std;

ll f[N];

int prime[8080],cnt,miu[N],s[N];

bool vis[N];

void init() {

	int i,j;

	miu[1]=s[1]=1;

	for(i=2;i<=50000;i++) {

		if(!vis[i]) {

			prime[++cnt]=i;

			miu[i]=-1;

		}

		for(j=1;j<=cnt&&i*prime[j]<=50000;j++) {

			vis[i*prime[j]]=1;

			if(i%prime[j]==0) {

				miu[i*prime[j]]=0;

				break;

			}

			miu[i*prime[j]]=-miu[i];

		}

		s[i]=s[i-1]+miu[i];

	}

	int lst;

	for(i=1;i<=50000;i++) {

		for(j=1;j<=i;j=lst+1) {

			lst=i/(i/j); f[i]+=1ll*(lst-j+1)*(i/j);

		}

	}

}

ll calc(ll n,ll m) {

	ll i,lst,r=min(n,m),ans=0;

	for(i=1;i<=r;i=lst+1) {

		lst=min(n/(n/i),m/(m/i));

		ans+=(s[lst]-s[i-1])*f[n/i]*f[m/i];

	}

	return ans;

}

int main() {

	init();

	int T;

	ll n,m;

	scanf("%d",&T);

	while(T--) {

		scanf("%lld%lld",&n,&m);

		printf("%lld\n",calc(n,m));

	}

}