Luogu P5221 Product

题目

注意一下空间限制。

令\(f(n)=\prod\limits_{i=1}^n\prod\limits_{j=1}^nij,g(n)=\prod\limits_{i=1}^n\prod\limits_{j=1}^n(i,j)\)

那么答案就是\(f(n)g(n)^{-2}\).

显然\(f(n)=(n!)^{2n}\)。

而\(g(n)=\prod\limits_{d=1}^nd^{\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum\limits_{j=1}^{\lfloor\frac nd\rfloor}[(i,j)=1]}=\prod\limits_{d=1}^nd^{\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}2\varphi(i)-1}\)。

然后就可以直接做了。

注意一下由于Euler定理指数部分的要对\(P-1\)取模。

#include<bits/stdc++.h>

using namespace std;

const int N=1000007,P=104857601,M=104857600;

int pr[N>>3],m,phi[N];bool f[N];

int inc(int a,int b){return a+=b,a>=M? a-M:a;}

int dec(int a,int b){return a-=b,a<0? a+M:a;}

int mul(int a,int b){return 1ll*a*b%P;}

int sqr(int a){return mul(a,a);}

int power(int a,int k){int r=1;for(;k;k>>=1,a=mul(a,a))if(k&1)r=mul(a,r);return r;}

int fac(int n){int s=1;for(;n;--n)s=mul(s,n);return s;}

int inv(int a){return power(a,P-2);}

int cal1(int n){return power(fac(n),n<<1);}

int cal2(int n)

{

    phi[1]=f[1]=1;int ans=1;

    for(int i=2,j,x;i<=n;++i)

    {

	if(!f[i]) pr[++m]=i,phi[i]=i-1;

	for(j=1;j<=m&&i*pr[j]<=n;++j)

	{

	    f[x=i*pr[j]]=1;

	    if(i%pr[j]) phi[x]=phi[i]*phi[pr[j]];

	    else {phi[x]=phi[i]*pr[j];break;}

	}

    }

    for(int i=2;i<=n;++i) phi[i]=inc(phi[i-1],phi[i]);

    for(int i=1;i<=n;++i) phi[i]=dec(inc(phi[i],phi[i]),1);

    for(int i=1;i<=n;++i) ans=mul(ans,power(i,phi[n/i]));

    return ans;

}

int main(){int n;cin>>n,cout<<mul(cal1(n),sqr(inv(cal2(n))));}

巴特西

Luogu P5221 Product

最新文章

热门文章