[SDOI2015]约数个数和

Description:

求$ sum_{i=1}^{n} sum_{j=1}^{m} d(ij) ( 其中)d(x)(表示)x$的约数个数

Hint:

(数据组数<=1e4,n,m<=5e4)

Solution:

首先有一个结论：

$d(ij)=sum_{x|i} sum_{y|j} [ gcd(x,y)==1 ] $

接着就推式子：

$ Ans=sum_{d}^{min(n,m)} mu(d) sum_{i=1}^{n} sum_{j=1}^{m} [d|gcd(i,j)] lfloor frac{n}{i} floor lfloorfrac{m}{i} floor $

从枚举d转为，枚举d*i ，这一步很重要

$ Ans=sum_{d}^{min(n,m)} mu(d) sum_{i=1}^{ lfloor frac{n}{d} floor } sum_{j=1}^{ lfloor frac{m}{d} floor } lfloor frac{n}{d*i} floor lfloor frac{m}{d*j} floor $

先用整除分块预处理出 (sum lfloor frac{n}{i} floor lfloorfrac{m}{i} floor)

再用整除分块算答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn=5e4+5;
int T,n,m,tot,vis[mxn],mu[mxn],p[mxn];
ll sum[mxn],s[mxn];

void sieve(int lim)
{
	mu[1]=1;
	for(int i=2;i<=lim;++i) {
		if(!vis[i]) mu[i]=-1,p[++tot]=i;
		for(int j=1;j<=tot,p[j]*i<=lim;++j) {
			vis[p[j]*i]=1;
			if(i%p[j]==0) {
				mu[p[j]*i]=0;
				break;
			}
			mu[p[j]*i]=-mu[i];
		}
	}
	for(int i=1;i<=lim;++i) sum[i]=sum[i-1]+mu[i];
	for(int i=1;i<=lim;++i) {
		for(int l=1,r;l<=i;l=r+1) {
			r=i/(i/l);
			s[i]+=1ll*(r-l+1)*(i/l); //预处理
		}
	}
}

int main()
{
	scanf("%d",&T);
	sieve(50000); int n,m;
	while(T--) {
		scanf("%d%d",&n,&m); 
		ll ans=0; if(n>m) swap(n,m);
		for(int l=1,r;l<=n;l=r+1) {
			r=min(n/(n/l),m/(m/l));
			ans+=1ll*(sum[r]-sum[l-1])*s[n/l]*s[m/l];
		}
		printf("%lld
",ans);
	}	
	return 0;
}