AT5200 [AGC038C] LCMs 莫比乌斯反演

LINK：LCMs

随便找了道题练习了一下莫比乌斯反演式子有两个地方化简错误导致查了1h的错。

讲一下大致思路容易发现直接做事\(n^2logn\)的。

观察得到数字集合大小为1e6.

可以设\(b_i\)表示i出现了多少次再进行计算LCM。

经过一些处理可以开始反演。

可以直接得到一个nlogn的做法。经过更换枚举顺序后之后nlogn预处理前缀和可以\(sqrt(n)\)求答案。

推式子的时候要小心一点很容易推错的。

const int MAXN=1000010,INV=(mod+1)>>1;

int n,maxx,top;

int a[MAXN],s[MAXN];

int v[MAXN],p[MAXN],mu[MAXN];

inline void prepare()

{

	mu[1]=1;

	rep(2,maxx,i)

	{

		if(!v[i])

		{

			p[++top]=i;

			v[i]=i;mu[i]=-1;

		}

		rep(1,top,j)

		{

			if(p[j]>maxx/i)break;

			v[p[j]*i]=p[j];

			if(v[i]==p[j])break;

			mu[p[j]*i]=-mu[i];

		}

	}

	rep(1,maxx,i)

	{

		int ww=maxx/i;

		rep(1,ww,j)s[i]=(s[i]+(ll)j*a[i*j])%mod;

	}

}

signed main()

{

	freopen("1.in","r",stdin);

	get(n);int cnt1=0,cnt2=0;

	rep(1,n,i){int get(x);++a[x];maxx=max(maxx,x);}

	prepare();int ans=0;

	rep(1,maxx,i)

	{

		cnt1=(cnt1+(ll)a[i]*a[i]%mod*i)%mod;

		cnt2=(cnt2+((ll)a[i]*(a[i]-1)/2)%mod*i)%mod;

		int ww=maxx/i;

		rep(1,ww,j)

		ans=(ans+(ll)mu[j]*j*j%mod*i%mod*s[(i*j)]%mod*s[(i*j)])%mod;

	}

	ans=(ll)(ans-cnt1+mod)*INV%mod;

	ans=(ans+cnt2)%mod;put(ans);

	return 0;

}

巴特西

AT5200 [AGC038C] LCMs 莫比乌斯反演

最新文章

热门文章