LOJ2565. 「SDOI2018」旧试题

给出\(A,B,C\),求\(\sum_{i=1}^{A}\sum_{j=1}^{B}\sum_{k=1}^C \sigma_0(ijk)\)。

\(\sigma_0(n)\)表示\(n\)的约数个数。

\(A,B,C\le 10^5\)


结论:\(\sigma_0(ijk)=\sum_{a|i}\sum_{b|j}\sum_{c|k}[b\perp c][a \perp c][a \perp b]\)。

证明类比只有两个数的情况。

接下来推式子,三项东西同步推,得到:\(\sum_i\sum_j\sum_k\mu(i)\mu(j)\mu(k)f(A,[j,k])f(B,[i,k])f(C,[i,j])\)

其中\(f(n,d)=\sum_{d|i}\frac{n}{i}\)。暴力求时间\(O(n\ln n)\)。

神仙转化:建图,找三元环\((i,j,k)\)。

建图的时候要求\(lcm\)不超过\(n\)。于是连出来的边实际上只有不到\(8*10^6\)条。

找三元环:求出每个点的度数,把边定向为从大度数到小度数。枚举某个点\(u\),先枚举\((u,w)\in E\)将\(w\)打上标记,再枚举\((u,v),(v,w)\in E\),若\(w\)有标记则找到一个三元环。

时间复杂度:其实相当于对于\((u,v)\in E\),给\(out_v\)求和。如果\(deg_v\le \sqrt m\),则\(out_v\le \sqrt m\),总共\(O(m\sqrt m)\);如果\(deg_v\ge \sqrt m\),这样的\(v\)或\(u\)不超过\(\sqrt m\)个,于是\(out_v\)最多被贡献\(\sqrt m\)次,总共也是\(O(m\sqrt m)\)。

还有更加神仙的不用找三元环的方法当然我不会……


using namespace std;
#include <bits/stdc++.h>
#define N 100005
#define ll long long
#define mo 1000000007
int gcd(int a,int b){
	int k;
	while (b)
		k=a%b,a=b,b=k;
	return a;
}
int lcm(int a,int b){
//	assert((ll)a/gcd(a,b)*b<=100005);
	return a/gcd(a,b)*b;
}
int A[3],n;
int p[N],np;
bool inp[N];
int mu[N],mnp[N];
void initp(int n){
	mu[1]=1;
	for (int i=2;i<=n;++i){
		if (!inp[i])
			p[++np]=i,mu[i]=-1,mnp[i]=i;
		for (int j=1;j<=np && i*p[j]<=n;++j){
			inp[i*p[j]]=1;
			mnp[i*p[j]]=p[j];
			if (i%p[j]==0)
				break;
			mu[i*p[j]]=-mu[i];
		}
	}
}
int f[3][N];
void initf(int g[],int n){
	for (int i=1;i<=n;++i){
		ll sum=0;
		for (int j=1;i*j<=n;++j)
			sum+=n/(i*j);
		g[i]=sum%mo;
	}
}
int deg[N];
struct EDGE{
	int to,w;
	EDGE *las;
} e[1000000];
int ne;
EDGE *last[N];
void link(int u,int v,int w){
	e[ne]={v,w,last[u]};
	last[u]=e+ne++;
}
struct edge{int u,v,w;} ed[1000000];
int q[N],re[N],totv,tote;
bool cmpq(int x,int y){return deg[x]>deg[y];}
ll ans;
void calc(int a){
	ll s=(ll)f[0][a]*f[1][a]%mo*f[2][a]%mo;
	ans+=mu[a]*s;
}
void calc(int a,int b,int ab){
	ll s=0;
	s+=(ll)f[0][b]*f[1][ab]%mo*f[2][ab];
	s+=(ll)f[0][ab]*f[1][b]%mo*f[2][ab];
	s+=(ll)f[0][ab]*f[1][ab]%mo*f[2][b];
	s%=mo;
	ans+=mu[a]*s;
}
void calc(int a,int b,int c,int ab,int ac,int bc){
	ll s=0;
	s+=(ll)f[0][ab]*f[1][ac]%mo*f[2][bc];
	s+=(ll)f[0][ab]*f[2][ac]%mo*f[1][bc];
	s+=(ll)f[1][ab]*f[0][ac]%mo*f[2][bc];
	s+=(ll)f[1][ab]*f[2][ac]%mo*f[0][bc];
	s+=(ll)f[2][ab]*f[0][ac]%mo*f[1][bc];
	s+=(ll)f[2][ab]*f[1][ac]%mo*f[0][bc];
	s%=mo;
	ans+=mu[a]*mu[b]*mu[c]*s;
}
int W,d[N],z[N],dz[N],cp;
void divide(int x){
	cp=0;
	while (x!=1){
		d[++cp]=mnp[x];
		z[cp]=0,dz[cp]=1;
		while (x%d[cp]==0)
			z[cp]++,x/=d[cp],dz[cp]*=d[cp];
	}
}
void find(int k,int u,int v){
	if (k>cp){
		if (u<v && mu[u] && mu[v]){
			ed[++tote]={u,v,W};
			deg[u]++,deg[v]++;
		}
		return;
	}
	int pro=1;
	for (int i=0;i<z[k];++i,pro*=d[k]){
		find(k+1,u*pro,v*dz[k]);
		find(k+1,u*dz[k],v*pro);
	}
	find(k+1,u*dz[k],v*dz[k]);
}
void work(){
	memset(deg,0,sizeof(int)*(n+1));
	totv=0,tote=0;
	for (int i=1;i<=n;++i){
		W=i;
		divide(i);
		find(1,1,1);
	}
	for (int i=1;i<=n;++i)
		if (mu[i])
			q[++totv]=i;
	sort(q+1,q+totv+1,cmpq);
	for (int i=1;i<=totv;++i)
		re[q[i]]=i;
	ne=0;
	memset(last,0,sizeof(EDGE*)*(n+1));
	for (int i=1;i<=tote;++i){
		int u=ed[i].u,v=ed[i].v;
		if (re[u]>re[v])
			swap(u,v);
		link(u,v,ed[i].w);
	}
	static int bz[N];
	for (int i=1;i<=totv;++i){
		int u=q[i];
		for (EDGE *ei=last[u];ei;ei=ei->las)
			bz[ei->to]=ei->w;
		for (EDGE *ei=last[u];ei;ei=ei->las){
			calc(u,ei->to,ei->w);
			calc(ei->to,u,ei->w);
			for (EDGE *ej=last[ei->to];ej;ej=ej->las)
				if (bz[ej->to])
					calc(u,ei->to,ej->to,ei->w,ej->w,bz[ej->to]);
		}
		for (EDGE *ei=last[u];ei;ei=ei->las)
			bz[ei->to]=0;
		calc(u);
	}
}
int main(){
//	freopen("in.txt","r",stdin);
	initp(100000);
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d%d%d",&A[0],&A[1],&A[2]);
		sort(A,A+3);
		n=A[2];
		for (int k=0;k<3;++k){
			memset(f[k],0,sizeof(int)*(n+1));
			initf(f[k],A[k]);
		}
		ans=0;
		work();	
		ans=(ans%mo+mo)%mo;
		printf("%lld\n",ans);
	}
	return 0;
}
上一篇:最新EI会议推荐:ICBCTIS2021诚邀您共聚长沙


下一篇:Codeforces 思维题汇总 2020(下篇)