洛谷 4917 天守阁的地板

这题其实没必要反演……
有 n∑i=1n∑j=1[gcd(i,j)=1]=2n∑i=1φ(i)−1，然后这题就没了……

好的，如果您看到了这里，请忽略以上内容。

首先题目要求 n∏i=1n∏j=1lcm(i,j)gcd(i,j)，根据小学奥数，把 lcm 拆开，得到 n∏i=1n∏j=1ijgcd2(i,j)。

由于是乘法，可以把分子和分母拆开，那么分子部分即 n∏i=1n∏j=1ij=(n!)2n。

然后看分母。
这十分套路啊…… n∏i=1n∏j=1gcd2(i,j)=(n∏i=1n∏j=1gcd(i,j))2=(n∏d=1dn∑i=1n∑j=1[gcd(i,j)=d])2

指数更熟悉了不是吗？
这个要是不会推就别说你会莫反。
得到 (n∏d=1dn∑i=1n∑j=1[gcd(i,j)=d])2=(n∏d=1d⌊nd⌋∑i=1μ(i)(⌊nid⌋)2)2

那么我们需要预处理 n∑i=1μ(i)(⌊ni⌋)2。
本来想 O(n√n) 预处理，但是考虑到 n≤106，需要做到 O(nlogn)。
想到了什么？
观察到对于 n∈[ki,(k+1)i)，有 ⌊ni⌋=k。
于是枚举倍数就可以了。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6;
const int mod = 19260817;
int T,n;
int vis[N + 5],prime[N + 5],cnt,mu[N + 5];
int fac[N + 5],f[N + 5];
int ans;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int main()
{
    mu[1] = 1;
    for(register int i = 2;i <= N;++i)
    {
        if(!vis[i])
            mu[prime[++cnt] = i] = -1;
        for(register int j = 1;j <= cnt && i * prime[j] <= N;++j)
        {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j]))
                break;
            else
                mu[i * prime[j]] = -mu[i];
        }
    }
    fac[0] = 1;
    for(register int i = 1;i <= N;++i)
    {
        fac[i] = (long long)fac[i - 1] * i % mod;
        for(register int j = 1;i * j <= N;++j)
            f[i * j] = (f[i * j] + (long long)mu[i] * j * j % (mod - 1)) % (mod - 1),f[min(i * (j + 1),N + 1)] = (f[min(i * (j + 1),N + 1)] - (long long)mu[i] * j * j % (mod - 1)) % (mod - 1);
    }
    for(register int i = 1;i <= N;++i)
        f[i] = (f[i - 1] + f[i] + mod - 1) % (mod - 1);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        ans = 1;
        for(register int l = 1,r;l <= n;l = r + 1)
        {
            r = n / (n / l);
            ans = (long long)ans * fpow((long long)fac[r] * fpow(fac[l - 1],mod - 2) % mod,f[n / l]) % mod;
        }
        printf("%d\n",(int)(((long long)fpow(fac[n],2 * n) * fpow(ans,mod - 3) % mod + mod) % mod));
    }
}