bzoj3529:[Sdoi2014]数表(莫比乌斯反演+树状数组)

Author Avatar
Sakits 4月 05, 2018

题解

  设F(n)F(n)nn为约数和,这个可以线性筛,也可以暴力O(nlogn)O(nlogn)算。

ans=i=1nj=1md=1nF(d)[(i,j)=d]=d=1nF(d)i=1nj=1m[(i,j)=d]=d=1nF(d)dkμ(kd)nkmk=k=1nnkmkdkF(d)μ(kd)\begin{aligned} ans&=\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^nF(d)[(i,j)=d]\\ &=\sum_{d=1}^nF(d)\sum_{i=1}^n\sum_{j=1}^m[(i,j)=d]\\ &=\sum_{d=1}^nF(d)\sum_{d|k}\mu(\frac{k}{d})\left \lfloor \frac{n}{k}\right \rfloor \left \lfloor \frac{m}{k}\right \rfloor\\ &=\sum_{k=1}^n\left \lfloor \frac{n}{k}\right \rfloor \left \lfloor \frac{m}{k} \right \rfloor \sum_{d|k} F(d)\mu(\frac{k}{d}) \end{aligned}

  因为有aa的限制,所以把F(n)F(n)排序,询问按aa排序,对每个询问把F(n)aF(n)\leq a的贡献插入树状数组后计算答案,复杂度O(nlog2n+Tnlogn)O(nlog^2n+T\sqrt{n}logn)
  取模的话直接自然溢出,最后对23112^{31}-1取与即可。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=500010, inf=1e9;
struct F{int f, pos;}f[maxn];
struct poi{int a, n, m, pos;}q[maxn];
int n, cntp, T;
int mu[maxn], pri[maxn], tree[maxn], ans[maxn];
bool v[maxn];
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
} 
bool operator < (poi a, poi b){return a.a<b.a;}
bool operator < (F a, F b){return a.f<b.f;}
inline void getmu(int n)
{
	mu[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!v[i]) mu[i]=-1, pri[++cntp]=i;
		for(int j=1;pri[j]*i<=n;j++)
		{
			v[pri[j]*i]=1;
			if(i%pri[j]==0)
			{
				mu[pri[j]*i]=0;
				break;
			}
			mu[pri[j]*i]=-mu[i];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j+=i) f[j].f+=i;
		f[i].pos=i;
	}
}
inline void update(int x, int delta){for(;x<=100000;x+=x&-x) tree[x]+=delta;}
inline int query(int x){int sum=0; for(;x;x-=x&-x) sum+=tree[x]; return sum;}
inline int getans(int n, int m)
{
	int ans=0;
	for(int i=1, last;i<=n;i=last+1)
	{
		last=min(n/(n/i), m/(m/i));
		ans+=(query(last)-query(i-1))*(n/i)*(m/i);
	}
	return ans;
}
int main()
{
	getmu(100000); read(T);
	for(int i=1;i<=T;i++) 
	read(q[i].n), read(q[i].m), read(q[i].a), q[i].pos=i;
	sort(q+1, q+1+T); sort(f+1, f+1+100000);
	for(int i=1, j=1;i<=T;i++)
	{
		while(f[j].f<=q[i].a && j<=100000)
		{
			for(int k=f[j].pos;k<=100000;k+=f[j].pos)
			update(k, f[j].f*mu[k/f[j].pos]);
			j++;
		}
		if(q[i].n>q[i].m) swap(q[i].n, q[i].m);
		ans[q[i].pos]=getans(q[i].n, q[i].m);
	}
	for(int i=1;i<=T;i++) printf("%d\n", ans[i]&0x7fffffff);
}