Luogu 4917 天守阁的地板（莫比乌斯反演+线性筛）

　　既然已经学傻了，这个题当然是上反演辣。

　　对于求积的式子，考虑把[gcd=1]放到指数上。一通套路后可以得到∏D∏d∏i∏j (ijd)(D=1~n,d|D,i,j=1~n/D)。

　　冷静分析一下，由μ*1=e，后面一串ij相关的式子仅当D=1时有贡献。这一部分就非常好算了。而d对某个D的贡献，容易发现是d。设f(D)=∏d(d|D)，这个式子是可以线性筛的。（事实上从莫比乌斯函数的性质上看好像也很可以求，然而已经不会了）筛完之后就可以愉快的整除分块了。

　　于是我们最后得到了一个不需要莫比乌斯函数的式子。复杂度O(n+t√nlogn)。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define P 19260817

#define N 1000010

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int T,n,fac[N],g[N],h[N],prime[N],cnt;

bool flag[N];

int ksm(int a,int k)

{

    if (k<) k=1ll*(P-)*(-k)%(P-);

    k%=(P-);

    int s=;

    for (;k;k>>=,a=1ll*a*a%P) if (k&) s=1ll*s*a%P;

    return s;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

    const char LL[]="%lld\n";

#else

    const char LL[]="%I64d\n";

#endif

    T=read();

    fac[]=;for (int i=;i<=;i++) fac[i]=1ll*fac[i-]*i%P;

    for (int i=;i<=;i++) fac[i]=ksm(fac[i],i);

    flag[]=;g[]=g[]=;

    for (int i=;i<=N-;i++)

    {

        if (!flag[i]) prime[++cnt]=i,g[i]=ksm(i,-);

        for (int j=;j<=cnt&&prime[j]*i<=N-;j++)

        {

            flag[prime[j]*i]=;

            if (i%prime[j]==) {g[prime[j]*i]=g[i];break; }

            g[prime[j]*i]=;

        }

    }

    for (int i=;i<=N-;i++) g[i]=1ll*g[i]*g[i-]%P;

    while (T--)

    {

        int n=read(),ans=1ll*fac[n]*fac[n]%P;

        for (int i=;i<=n;i++)

        {

            int t=n/(n/i);

            ans=1ll*ans*ksm(1ll*g[t]*ksm(g[i-],-)%P,2ll*(n/i)*(n/i)%(P-))%P;

            i=t;

        }

        cout<<ans<<endl;

    }

    return ;

}