<题解>P4917天守阁的地板

题

\begin{aligned} Ans &= \prod_a^n\prod_b^n \cfrac {lcm(a, b)^2} {ab}\\ &= \prod_a^n\prod_b^n \cfrac {ab} {\gcd(a, b)^2}\\ &= \cfrac {\prod_a^n\prod_b^n ab} {\prod_a^n\prod_b^n gcd(a, b)^2}\\ &= \cfrac {(n!)^{2n}} {\prod_a^n\prod_b^n gcd(a, b)^2} \end{aligned}

\begin{aligned} &\prod_a^n\prod_b^n gcd(a, b)^2\\ =&(\prod_d^n d^{\sum_a^n\sum_b^n [\gcd(a, b) = d]})^2\\ =&(\prod_d^n d^{\sum_a^{\frac n d}\sum_b^{\frac n d} [\gcd(a, b) = 1]})^2\\ =&(\prod_d^n d^{\sum_a^{\frac n d}\sum_b^{\frac n d} [\gcd(a, b) = 1]})^2\\ =&(\prod_d^n d^{(2\sum_i^{\frac n d}\varphi(i)) - 1})^2\\ =&(\prod_d^n d^{f(d)})^2&&f(d) = (2\sum_i^{\lfloor\frac n d\rfloor}\varphi(i)) - 1\\ =&\prod_d^n d^{2f(d)}\\ \end{aligned}

d可以数论分块

我是个傻子,忘了a^n\pmod p = a^{n\bmod\varphi(p)}\pmod p(a, p互质),因为p是个伟大的有意义的质数所以说\varphi(p) = p-1

#include <bits/stdc++.h>

const int mod = 19260817, N = 1000000 + 10;
long long phi[N], primes[N], phisum[N];
bool not_prime[N];

inline void pre_phi(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (!not_prime[i])
        {
            phi[i] = i - 1;
            primes[++primes[0]] = i;
        }
        for (int j = 1; j <= primes[0]; ++j)
        {
            if (i * primes[j] > n)
                break;
            not_prime[i * primes[j]] = true;
            if (i % primes[j] == 0)
            {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            else
                phi[i * primes[j]] = phi[i] * (primes[j] - 1); // phi[primes[j]]
        }
    }
    for (int i = 1; i <= n; ++i)
        phisum[i] = (phi[i] + phisum[i - 1]) % (mod - 1); // 指数取模
}

long long fact[N];
inline void pre_fact(int n)
{
    fact[0] = 1;
    for (int i = 1; i <= n; ++i)
        fact[i] = fact[i - 1] * i % mod;
}

long long power(long long a, int n)
{
    long long ret = 1;
    while (n)
    {
        if ( n & 1)
            ret = ret * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ret;
}

int inv(int val) { return power(val, mod - 2); }

inline int f(int n, int d)
{
    return (phisum[n / d] * 4 - 2 + mod - 1) % (mod - 1); // 指数取模
}

int main(void)
{
    pre_phi(N - 1);
    pre_fact(N - 1);
    int T;
    std::cin >> T;
    while (T--)
    {
        int n;
        std::cin >> n;
        long long ans2 = 1;
        for (int l = 1, r; l <= n; l = r + 1)
        {
            r = n / (n / l);
            ans2 = ans2 * power(fact[r] * inv(fact[l-1]) % mod, f(n, l)) % mod;
        }
        long long ans1 = power(fact[n], n * 2);
        std::cout << ans1 * inv(ans2) % mod << std::endl;
    }
}