洛谷 P6788 - 「EZEC-3」四月樱花（整除分块）

题意：

求

\[\prod\limits_{x=1}^n\prod\limits_{y|x}\frac{y^{d(y)}}{\prod\limits_{z|y}z+1} \pmod{p}
\]

\(1 \leq n \leq 10^9\)

\[y^{d(y)}=\prod_{z|y}y=\prod\limits_{z|y}z\times\frac{y}{z}=\prod\limits_{z|y}z^2
\]

然后

\[\begin{aligned}ans&=\prod\limits_{x=1}^n\prod\limits_{y|x}\frac{y^{d(y)}}{\prod\limits_{z|y}z+1}\\&=\prod\limits_{x=1}^n\prod\limits_{y|x}\prod\limits_{z|y}(\frac{z}{z+1})^2\\&=\prod_{z=1}^n(\frac{z}{z+1})^{2\times\sum\limits_{xyz \leq n}1}\\&=\prod_{z=1}^n(\frac{z}{z+1})^{2\times\sum\limits_{y \leq \frac{n}{z}}\lfloor\frac{n}{yz}\rfloor}\end{aligned}
\]

令 \(f(i)=\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor\)，那么 \(ans=\prod_{z=1}^n(\frac{z}{z+1})^{2\times f(\lfloor\frac{n}{z}\rfloor)}\)。

\(f(i)\) 显然可以用整除分块来搞。我们发现外面枚举 \(z\) 的部分也可以使用整除分块，因此可以想到整除分块套整除分块，时间复杂度 \(\mathcal O(n^{\frac{3}{4}})\)

借鉴杜教筛的优化方法，可以预处理出 \([1,n^{\frac{2}{3}}]\) 的 \(f(i)\)，这样总时间复杂度就变为 \(\mathcal O(n^{\frac{2}{3}})\)

/*

Contest: -

Problem: P6788

Author: tzc_wk

Time: 2020.9.19

*/

#include <bits/stdc++.h>

using namespace std;

#define fi			first

#define se			second

#define pb			push_back

#define fz(i,a,b)	for(int i=a;i<=b;i++)

#define fd(i,a,b)	for(int i=a;i>=b;i--)

#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)

#define all(a)		a.begin(),a.end()

#define fill0(a)	memset(a,0,sizeof(a))

#define fill1(a)	memset(a,-1,sizeof(a))

#define fillbig(a)	memset(a,0x3f,sizeof(a))

#define y1			y1010101010101

#define y0			y0101010101010

#define int long long

typedef pair<int,int> pii;

typedef long long ll;

inline int read(){

	int x=0,neg=1;char c=getchar();

	while(!isdigit(c)){

		if(c=='-') neg=-1;

		c=getchar();

	}

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return x*neg;

}

int n=read(),mod=read();

inline int qpow(int x,int e){

	x%=mod;int ans=1;

	while(e){

		if(e&1) ans=ans*x%mod;

		x=x*x%mod;e>>=1;

	}

	return ans;

}

int f[1000005];

inline int calc(int x){

	if(x<=1000000) return f[x];

	int sum=0;

	for(int l=1,r;l<=x;l=r+1){

		r=x/(x/l);

		sum=(sum+(x/l)%(mod-1)*(r-l+1)%(mod-1))%(mod-1);

	}

	return sum;

}

inline void prework(int m){

	fz(i,1,m) for(int j=i;j<=m;j+=i) f[j]++;

	fz(i,1,m) f[i]=(f[i]+f[i-1])%(mod-1);

}

signed main(){

	prework(1000000);int ans=1;

	for(int l=1,r;l<=n;l=r+1){

		r=n/(n/l);

		int xx=qpow((r+1)%mod,mod-2)*(l%mod)%mod;xx=xx*xx%mod;

		ans=ans*qpow(xx,calc(n/l))%mod;

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

洛谷 P6788 - 「EZEC-3」四月樱花（整除分块）

最新文章

热门文章