首页 > 代码库 > BZOJ 3994: [SDOI2015]约数个数和

BZOJ 3994: [SDOI2015]约数个数和

3994: [SDOI2015]约数个数和

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 898  Solved: 619
[Submit][Status][Discuss]

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

Source

Round 1 感谢yts1999上传

分析:

首先$d(x)$是一个积性函数,其次这个东西有一个很神奇的性质:

$d(nm)=\sum _{x\mid n} \sum _{y\mid m} [gcd(x,y)==1]$

证明如下:(懒得写了...公式打起来好麻烦...直接摘抄Sengxian的解释...QwQ)

技术分享

于是接下来就直接莫比乌斯反演就好了...

$\sum _{x=1}^{n} \sum _{y=1}^{m} \left \lfloor \frac{n}{x} \right \rfloor \left \lfloor \frac{m}{y} \right \rfloor \sum _{d\mid x  d\mid y}\mu (d)$

$=\sum _{d=1}^{x} \mu(d) \sum _{i=1}^{\frac {n}{d}} \left \lfloor \frac{n}{id} \right \rfloor \sum _{j=1}^{\frac {m}{d}} \left \lfloor \frac{m}{jd} \right \rfloor$

现在有一个有用的公式:

$\left \lfloor \frac{n}{xy} \right \rfloor=\left \lfloor \frac{ \left \lfloor \frac{n}{x} \right \rfloor }{y} \right \rfloor$

于是乎,我们定义$f(x)=\sum _{i=1}^{x} \left \lfloor \frac{x}{i} \right \rfloor$,

那么式子就变成酱紫:

$\sum _{d=1}^{n} \mu(d) f(\left \lfloor \frac{n}{d} \right \rfloor) f(\left \lfloor \frac{m}{d} \right \rfloor)$

时间复杂度:$O(N\sqrt{N}+T\sqrt{N})$

代码:

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>//by NeighThornusing namespace std;const int maxn=50000+5;int n,m,cas,cnt,mu[maxn],pri[maxn],vis[maxn];long long ans,f[maxn];inline long long calc(int x){	long long res=0;	for(int i=1,r;i<=x;i=r+1){		r=x/(x/i);		res+=(x/i)*(r-i+1);	}	return res;}inline void prework(void){	mu[1]=1;	for(int i=2;i<=50000;i++){		if(!vis[i])			vis[i]=1,pri[++cnt]=i,mu[i]=-1;		for(int j=1;j<=cnt&&i*pri[j]<=50000;j++){			vis[i*pri[j]]=1;			if(i%pri[j]==0){				mu[i*pri[j]]=0;break;			}			mu[i*pri[j]]=-mu[i];		}	}	for(int i=1;i<=50000;i++) mu[i]+=mu[i-1],f[i]=calc(i);}signed main(void){	scanf("%d",&cas);prework();	while(cas--){		scanf("%d%d",&n,&m);		if(n>m) swap(n,m);ans=0;		for(int i=1,r;i<=n;i=r+1){			r=min(n/(n/i),m/(m/i));			ans+=f[n/i]*f[m/i]*(mu[r]-mu[i-1]);		}		printf("%lld\n",ans);	}	return 0;}

  


By NeighThorn

BZOJ 3994: [SDOI2015]约数个数和