luogu4917天守阁的地板

数论 分块

---

题面

给出$n$，用所有长为$a$、宽为$b$$(1\leq a,b\leq n)$的长方形拼成正方形,最少需多少块？
多组数据。

• $30pts$ $n\leq100,T\leq100$
• $60pts$ $n\leq3*10^4,T\leq300$
• $100pts$ $a,b\leq10^5,T\leq1000$

解析

显然答案是

$$\frac{lcm(a,b)}{a}*\frac{lcm(a,b)}{b}$$
暴力复杂度$O(Tn^2logn)$，可以通过$30pts$。

考虑推推柿子。

$$\prod_{a=1}^n\prod_{b=1}^n\frac{lcm(a,b)}{a}*\frac{lcm(a,b)}{b}$$
$$=\prod_{a=1}^n\prod_{b=1}^n\frac{lcm^2(a,b)}{ab}$$
$$=\prod_{a=1}^n\prod_{b=1}^n\frac{ab}{gcd^2(a,b)}$$
$$=\frac{(n!)^{2n}}{\prod_{a=1}^n\prod_{b=1}^ngcd^2(a,b)}$$

现在问题是$\prod_{a=1}^n\prod_{b=1}^ngcd(a,b)$。
这个复杂度$O(n^2)$，很不划算。
考虑枚举最大公约数的值。
则化为

$$\prod_{d=1}^nd^{\sum_{a=1}^n\sum_{b=1}^n[gcd(a,b)==d]}$$
$$\prod_{d=1}^nd^{\sum_{a=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{b=1}^{\lfloor\frac{n}{d}\rfloor}[gcd(a,b)==1]}$$
这个指数怎么化呢？
我们可以强制$a>b$，那么指数为$\sum_{a=1}^{\lfloor\frac{n}{d}\rfloor}\varphi(a)$
如果不强制，考虑到$\varphi(1)=1$的特殊情况，柿子可化为：
$$\prod_{d=1}^nd^{[\sum_{a=1}^{\lfloor\frac{n}{d}\rfloor}2*\varphi(a)]-1}$$
然后线性预处理一下欧拉函数前缀和，这样复杂度$O(Tn)$，$60pts$稳了。

然后吗，注意到$\lfloor\frac{n}{d}\rfloor$在一段区间内是相同的，可以数论分块。
于是就做完了。
预处理逆元后，复杂度$O(T\sqrt n$)。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=19260817,N=1e6+100;
int a,b,jc[N],pri[N],ol[N],n,tot,inv[mod+100];
ll ans,gu;
bool vis[N];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il ll ksm(re ll S,re ll n)
{
  re ll T=S;S=1;
  if(n<0) return 0;
  while(n)
    {
      if(n&1) S=S*T%mod;
      T=T*T%mod;
      n>>=1;
    }
  return S;
}
il void Pre(re int n)
{
  ol[1]=1;
  fp(i,2,n)
    {
      if(!vis[i]) pri[++tot]=i,ol[i]=i-1;
      for(re int j=1;j<=tot&&i*pri[j]<=n;++j)
    {
      vis[i*pri[j]]=1;
      if(i%pri[j]) ol[i*pri[j]]=ol[i]*(pri[j]-1);
      else {ol[i*pri[j]]=ol[i]*pri[j];break;}
    }
    }
  fp(i,1,n) (ol[i]+=ol[i-1])%=(mod-1);
  jc[0]=1;fp(i,1,n) jc[i]=1ll*jc[i-1]*i%mod;
  inv[0]=inv[1]=1;fp(i,2,mod) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
}     
int main()
{
  re int T=gi();
  Pre(1e6);
  while(T--)
    {
      n=gi();
      ans=ksm(jc[n],2*n);gu=1;
      re int L=0;
      for(re int i=1;i<=n;i=L+1)
    {
      L=n/(n/i);
      (gu*=ksm(1ll*jc[L]*inv[jc[i-1]]%mod,2*ol[n/i]-1))%=mod;
    }
      (ans*=inv[gu*gu%mod])%=mod;
      printf("%lld\n",ans);
    }
  return 0;
}