luogu4917天守阁的地板

https://www.zybuluo.com/ysner/note/1317548---

题面

给出$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;

}

巴特西

luogu4917天守阁的地板

题面

解析

最新文章

热门文章