2017-02-27

【bzoj3529】数表

本文为博主原创，未经许可不得转载

AC通道

题解

我们先考虑如果没有a的限制条件的情况：

设n<m

令$F(i)$表示i的约数和，则$F(i)$可以在$O(n\log(n))$的时间内求出来（POPOQQQ大爷有一种$O(n)$的方法）

令$g(i)$表示$\gcd(x,y)=i$的数对$(x,y)$的个数，则通过莫比乌斯反演可得 $g(i)=\sum_{i|d}^{ }\mu(\frac{d}{i})\left [ \frac{n}{d} \right ]\left [ \frac{m}{d} \right ]$

则 $ans=\sum_{i=1}^{n}F(i)g(i)=\sum_{i=1}^{n}F(i)\sum_{i|d}^{ }\mu(\frac{d}{i})\left [ \frac{n}{d} \right ]\left [ \frac{m}{d} \right ]=\sum_{d=1}^{n}\left [ \frac{n}{d} \right ]\left [ \frac{m}{d} \right ]\sum_{i|d}^{ }F(i)\mu(\frac{d}{i})$

所以我们只需要计算出 $\sum_{i|d}^{ }F(i)\mu(\frac{d}{i})$ 的前缀和就行了

然而现在有a的限制，怎么做呢？

我们发现对答案有贡献的$i$只有$F(i)<=a$的$i$

所以我们离线处理，将$F(i)$排序，将询问按$a$排序

每次询问前将满足$F(i)<=a$的$i$插入到树状数组中，然后查询。

时间复杂度：$O(n\log^2{n}+q\sqrt{n}\log{n})$

参考代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
#define FILE "read"
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
const int MAXN=(int)1e5,D(50);
struct node{
	int n,m,a,id;
	bool operator < (const node &b) const {return a<b.a;}
}Q[MAXN+D];
int T,cnt,maxx,mu[MAXN+D],prime[MAXN+D],check[MAXN+D],tr[MAXN+D],ans[MAXN+D];
pair<int,int>f[MAXN+D];
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,f=1;  char ch=getc();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
		return x*f;
	}
}using namespace INIT;
void add(int x,int v){while(x<=maxx)tr[x]+=v,x+=(x&-x);}
int get(int x){int sum(0);while(x)sum+=tr[x],x-=(x&-x);return sum;}
void pre(){
	mu[1]=1;
	for(int i=2;i<=maxx;++i){
		if(!check[i])  prime[++cnt]=i,mu[i]=-1;
		for(int j=1;j<=cnt&&prime[j]*i<=maxx;++j){
			check[prime[j]*i]=1;
			if(i%prime[j]==0)  {mu[i*prime[j]]=0; break;}
			mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<=maxx;++i)
		for(int j=i;j<=maxx;j+=i)  f[j].first+=i;
	for(int i=1;i<=maxx;++i)  f[i].second=i;
}
void solve(int x){
	int n=Q[x].n,m=Q[x].m;
	for(int i=1,last;i<=n;i=last+1){
		last=min(n/(n/i),m/(m/i));
		ans[Q[x].id]+=(n/i)*(m/i)*(get(last)-get(i-1));
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	T=read();  
	for(int i=1;i<=T;++i){
		Q[i].n=read(); Q[i].m=read(); Q[i].a=read(); Q[i].id=i;
		if(Q[i].n>Q[i].m)  swap(Q[i].n,Q[i].m);
		cmax(maxx,Q[i].n);
	}
	pre(); 
	sort(Q+1,Q+T+1);  sort(f+1,f+maxx+1); int now(0);
	for(int i=1;i<=T;++i){
		while(now<maxx&&f[now+1].first<=Q[i].a){
			for(int j=f[++now].second;j<=maxx;j+=f[now].second)
				add(j,f[now].first*mu[j/f[now].second]);
		}
		solve(i);
	}
	for(int i=1;i<=T;++i)  printf("%d\n",ans[i]&0x7fffffff);
	return 0;
}

本文标题:【bzoj3529】数表

文章作者:chty

发布时间:2017年02月27日 - 21时41分

最后更新:2018年03月02日 - 17时22分

许可协议:本文为博主原创，未经许可不得转载。