自动搬运

查看原文

来自洛谷，原作者为

	jszjinshengzhi **

搬运于2025-08-24 22:05:15，当前版本为作者最后更新于2018-10-17 19:58:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Luogu P4917 天守阁的地板

题意：给定$n$，求用$a\times b(1\le a,b\le n)$的木板铺出一个最小的正方形所消耗木板的数量。为了避免高精，只用求范围内所有的$a,b$对应的答案的积（答案对长者生日19260817）。

数据范围：多组数据，$T\le1000,n\le1000000$

分析：对于$a\times b$的木板，能铺成的最小正方形的边长为$lcm(a,b)$，所用木板数即为$\frac{lcm(a,b)^2}{a\cdot b}$

所以 $Ans=\prod_{a=1}^n\prod_{b=1}^n\frac{lcm(a,b)^2}{a\cdot b}$

接下来就是暴力推柿子了。

看着$lcm$就特别不爽，于是把它换成$gcd$。

注意到$lcm(a,b)=\frac{a\cdot b}{gcd(a,b)}$，代入，有$Ans=\prod_{a=1}^n\prod_{b=1}^n\frac{a\cdot b}{gcd(a,b)^2}$

直接把分数化开来推想想都觉得很麻烦，而分子部分只有$a,b$两个字母，求积就是个阶乘的$2n$次幂，分母$gcd$又有很多现成的套路，看着多舒服，干脆直接把分子分母拆开来算。

分子$=(n!)^{2\cdot n}$

分母$=\prod_{a=1}^n\prod_{b=1}^ngcd(a,b)^2=(\prod_{d=1}^nd^{\sum_{a=1}^{\lfloor\frac nd\rfloor}\sum_{b=1}^{\lfloor\frac nd\rfloor}gcd(a,b)==1})^2\qquad$（枚举$gcd$）

$=\prod_{d=1}^nd^{4\cdot\sum_{i=1}^{\lfloor\frac nd\rfloor}\varphi(i)-2}=(n!)^{-2}\cdot\prod_{d=1}^nd^{4\cdot\sum_{i=1}^{\lfloor\frac nd\rfloor}\varphi(i)}$

分母中的$n!$提到分子，就可以开始开心的整除分块了，只需$O(n)$预处理筛出$\varphi$的前缀和、阶乘、逆元即可。

复杂度：$O(T\cdot\sqrt n)$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define p 19260817

inline ll fpow(ll a,ll b){
	ll ret=1;
	for(;b;ret*=((b&1)?a:1),ret%=p,a=a*a%p,b>>=1);
	return ret;
}

#define maxn 1000005
ll phi[maxn],fac[maxn];
ll cnt,prime[maxn];
inline void init(){
	phi[1]=1;
	for(ll i=2;i<maxn;++i){
		if(!phi[i]){
			phi[i]=i-1;
			prime[++cnt]=i;
		}
		for(ll j=1;j<=cnt&&prime[j]*i<maxn;++j){
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			phi[i*prime[j]]=phi[i]*phi[prime[j]];
		}
	}
	fac[0]=1;
	for(ll i=1;i<maxn;++i){
		phi[i]=(phi[i]+phi[i-1])%(p-1);//！！！这里模的是p-1，因为phi出现在指数中！！！ 
		fac[i]=fac[i-1]*i%p;
	}
}

int T;
ll n,ans;
int main(){
	init();
	scanf("%d",&T);
	while(T--){
		scanf("%lld",&n);
		ans=1;
		for(ll l=1,r;l<=n;l=r+1){
			r=n/(n/l);
			ans=ans*fpow(fac[r]*fpow(fac[l-1],p-2)%p,phi[n/l])%p;
		}
		printf("%lld\n",fpow(fac[n],2*n+2)*fpow(ans,p-5)%p);//这里的fpow(ans,p-5)表示ans^4的逆元
	}
	return 0;
}