P4917 天守阁的地板 & P5221 Product

，莫反の卡密哒！

题目简介

题目名称：Product
题目来源：

评测链接：https://www.luogu.com.cn/problem/P5221

形式化题意：求 ，模数 。

数据范围：

时空限制：

卡常不多测版

第一次见数学题卡常的，还时间空间一起卡。

来化简！（大量 注意）

$$\begin{align} ans&=\nonumber \prod_{i=1}^{n}\prod_{j=1}^{n}\frac{i\times j}{\gcd(i,j)^2} \\ \prod_{i=1}^{n}\prod_{j=1}^{n}i\times j &=\nonumber \prod_{i=1}^{n}i^{n}\prod_{j=1}^{n}j \\ &=\nonumber (n!)^{2n} \\ \prod_{i=1}^{n}\prod_{j=1}^{n}\gcd(i,j) &=\nonumber \prod_{i=1}^{n}\prod_{j=1}^{n}\prod_{d=1}d^{[\gcd(i,j)=d]} \\ &=\nonumber \prod_{d=1}\prod_{i=1}^{n}\prod_{j=1}^{n}d^{[\gcd(i,j)=d]} \\ &=\nonumber \prod_{d=1}d^{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} [\gcd(i,j)=d] } \\ &=\nonumber \prod_{d=1}d^{\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor} [\gcd(i,j)=1] } \\ &=\nonumber \prod_{d=1}d^{\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor} \sum\limits_{k\mid i,k\mid j}\mu(k) } \\ &=\nonumber \prod_{d=1}d^{\sum\limits_{k=1}\sum\limits_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{kd}\rfloor}\mu(k) } \\ &=\nonumber \prod_{d=1}d^{\sum\limits_{k=1}\mu(k)\sum\limits_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{kd}\rfloor} } \\ &=\nonumber \prod_{k=1}^{n}\prod_{d=1}^{\lfloor\frac{n}{k}\rfloor}d^{\mu(k)\lfloor\frac{n}{kd}\rfloor^2} \\ ans&=\nonumber \frac{(n!)^{2n}}{\left(\displaystyle\prod_{k=1}^{n}\prod_{d=1}^{\lfloor\frac{n}{k}\rfloor}d^{\mu(k)\lfloor\frac{n}{kd}\rfloor^2}\right)^2} \end{align}$$

---

上面有大量 请注意！

虽然看起来很复杂，但是时间复杂度是对的，分子可以在线性时间内求出阶乘，并用快速幂做到 。分母枚举 为线性，但是枚举 保证了计算在调和级数时间复杂度内，而虽然最后会套一个逆元（莫比乌斯函数）和快速幂，但通过乘方的性质，我们可以再套一层，变成：

$$ans=\nonumber \frac{(n!)^{2n}}{\left(\displaystyle\left(\prod_{k=1}^{n}\prod_{d=1}^{\lfloor\frac{n}{k}\rfloor}d\right)^{\mu(k)\lfloor\frac{n}{kd}\rfloor^2}\right)^2} \nonumber$$

从而使得逆元和快速幂的时间复杂度不会再套一个 ，最终的时间复杂度为 ，总之，是可以卡过的（本地最高 ），比较惊险。

分子是好做的，主要考虑反演 。

有 步的思想不太能想到：

一是将 转换为指数，容易发现两层 中的只会对 以及 的指数做限制，考虑 对于 而言让 被算了多少次，然后提为指数，一般而言，是 的形式。（这个表示是艾弗森记号表示法）

二是将 指数转为底数，同样用到了上述公式的逆变换，也属于莫反 的常见变换。

据说这道题能加强数据到 有线性做法，继续推公式可以数论分块，但也已经够毒瘤了。

然后有一个被卡成暴力的错误点，是欧拉定理： ，也就是模运算下，指数应取模 ，这已经是第三次在这个地方犯错了，以后要注意。

AC Code

// ----- Eternally question-----
// Problem: P5221 Product
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5221
// Memory Limit: 7 MB
// Time Limit: 200 ms
// Written by: Eternity
// Time: 2023-01-05 08:36:46
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e6+10;
const int Mod=104857601;
int N;
int pri[MAXN],Tot,Mu[MAXN];
bool is[MAXN];
inline ll qPow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%Mod;
		a=a*a%Mod;b>>=1;
	}
	return res;
}
inline void sieve(int n)
{
	is[1]=1,Mu[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!is[i]) pri[++Tot]=i,Mu[i]=-1;
		for(int j=1;j<=Tot&&i*pri[j]<=n;++j)
		{
			is[i*pri[j]]=1;
			if(i%pri[j]==0)
			{
				Mu[i*pri[j]]=0;
				break;
			}
			Mu[i*pri[j]]=-Mu[i];
		}
	}
}
ll f[MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	sieve(N+1);
	ll ans1=1,ans2=1;
	for(int i=1;i<=N;++i) ans1=1ll*ans1*i%Mod;
	ans1=qPow(ans1,2ll*N);
	for(int k=1;k<=N;++k)
	{
		if(!Mu[k]) continue;
		ll sum=1;
		for(int d=1;1ll*d*k<=N;++d)
		{
			int x=1ll*k*d%Mod;
			sum=sum*qPow(d,1ll*(N/x)*(N/x)%(Mod-1))%Mod;
		}
		if(Mu[k]==1) ans2=1ll*ans2*sum%Mod;
		else ans2=1ll*ans2*qPow(sum,Mod-2)%Mod;
	}
	write(1ll*ans1*qPow(1ll*ans2*ans2%Mod,Mod-2)%Mod);
	return 0;
}
/*

*/

---

不卡常多测版

题目简介

题目名称：天守阁的地板
题目来源：

评测链接：https://www.luogu.com.cn/problem/P4917

形式化题意：记 为大小为 的长方形组成任意边长正方形的最少个数，求 ，多测。

数据范围：

容易发现， 是容易计算的，得到 ，那就和上面那道题是一样的了，可惜是多测，线性过不了。

那考虑优化！

我们重新推式子：

$$\begin{align} ans &=\nonumber \prod_{d=1}d^{\sum\limits_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\sum\limits_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{kd}\rfloor} } \\ &=\nonumber \prod_{d=1}d^{\sum\limits_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\lfloor\frac{n}{kd}\rfloor^2} \end{align}$$

我们不急着将 移下来，因为上道题的经验告诉我们那样子至少时间复杂度也是 级别的。所以我们将指数单独考虑，尝试优化。

记录 ，那么，我们可以把答案表示为：

$$ans=\prod_{d=1}^{n}d^{f(\lfloor\frac{n}{d}\rfloor)} \nonumber$$

对于 本身，我们可以数论分块将其在 的时间内计算得出。而容易发现， 函数本身也具有数论分块的性质，多以我们可以在进行计算 的时候对 进行数论分块，达到降低复杂度的效果。

最后时间复杂度为 。

AC Code

// ----- Eternally question-----
// Problem: P4917 天守阁的地板
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4917
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2023-01-05 10:30:45
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e6+10;
const int Mod=19260817;
int N;
int pri[MAXN],Tot,Mu[MAXN],Sum_Mu[MAXN];
bool is[MAXN];
inline ll qPow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%Mod;
		a=a*a%Mod;b>>=1;
	}
	return res;
}
inline void sieve(int n)
{
	is[1]=1,Mu[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!is[i]) pri[++Tot]=i,Mu[i]=-1;
		for(int j=1;j<=Tot&&i*pri[j]<=n;++j)
		{
			is[i*pri[j]]=1;
			if(i%pri[j]==0)
			{
				Mu[i*pri[j]]=0;
				break;
			}
			Mu[i*pri[j]]=-Mu[i];
		}
	}
	for(int i=1;i<=n;++i) Sum_Mu[i]=Sum_Mu[i-1]+Mu[i];
}
int Test;
ll f[MAXN],g[MAXN];
ll Mul[MAXN],Inv[MAXN];
inline void init(int n)
{
	sieve(n);
	Inv[0]=Mul[0]=Mul[1]=1;
	for(int i=2;i<=n;++i) Mul[i]=Mul[i-1]*i%Mod;
	Inv[n]=qPow(Mul[n],Mod-2);
	for(int i=n-1;i>=1;--i) Inv[i]=Inv[i+1]*(i+1)%Mod;
	// for(int i=1;i<=10;++i) write(Mul[i],' ');puts("");
	// for(int i=1;i<=10;++i) write(Inv[i],' ');puts("");
	// for(int i=1;i<=10;++i) write(Sum_Mu[i],' ');puts("");
}
ll rem[MAXN];
inline ll calc(int n)
{
	if(rem[n]) return rem[n];
	ll res=0;
	for(int l=1,r;l<=n;l=r+1)
	{
		r=std::min(n,n/(n/l));
		res+=1ll*(Sum_Mu[r]-Sum_Mu[l-1])*(n/l)*(n/l);
		// write("res:",res,'\n');
		// res=(res+1ll*(Sum_Mu[r]-Sum_Mu[l-1]+(Mod-1))%(Mod-1)*(n/l)%(Mod-1)*(n/l)%(Mod-1))%(Mod-1);
	}
	return rem[n]=res;
}
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	init(MAXN-10);
	while(Test--)
	{
		read(N);
		ll ans=1;
		for(int l=1,r;l<=N;l=r+1)
		{
			r=std::min(N,N/(N/l));
			ans=ans*qPow(Mul[r]*Inv[l-1]%Mod,calc(N/l))%Mod;
			// write("l:",l,' ',N/l,' ',calc(N/l),'\n');
		}
		write(qPow(Mul[N],2ll*N)*qPow(ans*ans%Mod,Mod-2)%Mod,'\n');
	}
	return 0;
}
/*

*/

---

据说这道题有欧拉反演的做法，可惜不会。