P7486 「Stoi2031」彩虹

P7486 「Stoi2031」彩虹

$$
\begin {aligned}
\prod _ {i = 1} ^ n \prod _ {j = 1} ^ m \mathrm {lcm} (i, j) ^ {\mathrm {lcm} (i, j)} & = \prod _ {i = 1} ^ n \prod _ {j = 1} ^ m (\frac {ij} {(i, j)}) ^ {\frac {ij} {(i, j)}} \\
& = \prod _ {d = 1} ^ n \prod _ {i = 1} ^ n \prod _ {j = 1} ^ m (\frac {ij} d) ^ {\frac {ij} d [(i, j) = d]} \\
& = \prod _ {d = 1} ^ n \prod _ {i = 1} ^ {\lfloor \frac n d \rfloor } \prod _ {j = 1} ^ {\lfloor \frac m d \rfloor } (ijd) ^ {ijd [(i, j) = 1]} \\
& = \prod _ {d = 1} ^ n \prod _ {i = 1} ^ {\lfloor \frac n d \rfloor } \prod _ {j = 1} ^ {\lfloor \frac m d \rfloor } (ijd) ^ {ijd \sum _ {k | (i, j)} \mu(k)} \\
& = \prod _ {d = 1} ^ n \prod _ {k = 1} ^ n \prod _ {i = 1} ^ {\lfloor \frac n {kd} \rfloor } \prod _ {j = 1} ^ {\lfloor \frac m {kd} \rfloor } (ijdk ^ 2) ^ {ijdk ^ 2 \mu(k)} \\
& = \prod _ {T = 1} ^ n \prod _ {k | T} \prod _ {i = 1} ^ {\lfloor \frac n T \rfloor } \prod _ {j = 1} ^ {\lfloor \frac m T \rfloor } (ijTk) ^ {ijTk \mu(k)} \\
& = \prod _ {T = 1} ^ n (\prod _ {i = 1} ^ {\lfloor \frac n T \rfloor } \prod _ {j = 1} ^ {\lfloor \frac m T \rfloor } (ij) ^ {ijT\sum _ {k | T} k\mu(k)}) (T ^ {\sum _ {k | T} \mu(k)} \prod _ {k | T} k ^ {k \mu(k)}) ^ {T\sum _ {i = 1} ^ {\lfloor \frac n T \rfloor } \sum _ {j = 1} ^ {\lfloor \frac m T \rfloor }}
\end {aligned}
$$

记 $f _ n = \sum _ {i = 1} ^ n i ^ i$ ，$s _ n = \sum _ {i = 1} ^ n i$ 。$c(n, m) = \prod _ {i = 1} ^ n \prod _ {j = 1} ^ m (ij) ^ {ij} = \prod _ {i = 1} ^ n \prod _ {j = 1} ^ m (i ^ i) ^ j (j ^ j) ^ i = (\prod _ {i = 1} ^ n (i ^ i) ^ {s _ m}) (\prod _ {i = 1} ^ m (i ^ i) ^ {s _ n}) = f _ n ^ {s _ m} f _ m ^ {s _ n} $ 。

那么原式有：

$$
\prod _ {T = 1} ^ n c(\lfloor \frac n T \rfloor, \lfloor \frac m T \rfloor) ^ {T\sum _ {k | T} k\mu(k)} (T ^ {\sum _ {k | T} \mu(k)} \prod _ {k | T} k ^ {k \mu(k)}) ^ {T s _ {\lfloor \frac n T \rfloor } s _ {\lfloor \frac m T \rfloor }}
$$

剩下的 $T\sum _ {k | T} k\mu(k), (T ^ {\sum _ {k | T} \mu(k)} \prod _ {k | T} k ^ {k \mu(k)}) ^ T$ 是关于 $T$ 的式子，可以在 $O(n\ln n)$ 的时间内预处理，前缀和、前缀积，数论分块。

复杂度 $O(n \ln n + T \sqrt n \log p)$ 。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
typedef long long LL;
const int N = 1e6 + 10, mod = 32465177;
bool vis[N];
int cnt, p[N], mu[N], s[N], f[N], g[N], h[N];
int binpow (int b, int k = mod - 2)
{
    (k %= mod - 1) += mod - 1;
    int res = 1;
    for (; k; k >>= 1, b = (LL)b * b % mod)
        if (k & 1) res = (LL)res * b % mod;
    return res;
}
void init ()
{
    vis[1] = true;
    mu[1] = 1;
    for (int i = 2; i < N; ++i)
    {
        if (!vis[i]) mu[p[++cnt] = i] = -1;
        for (int j = 1; j <= cnt && i * p[j] < N; ++j)
        {
            vis[i * p[j]] = true;
            if (i % p[j] == 0) break;
            mu[i * p[j]] = -mu[i];
        }
    }
    for (int i = 1; i < N; ++i)
        s[i] = (s[i - 1] + i) % (mod - 1);
    f[0] = 1;
    for (int i = 1; i < N; ++i)
        f[i] = (LL)f[i - 1] * binpow(i, i) % mod;
    for (int i = 1; i < N; ++i) if (mu[i])
        for (int j = i, t = i * mu[i]; j < N; j += i)
            (g[j] += t) %= (mod - 1);
    for (int i = 0; i < N; ++i) h[i] = 1;
    for (int i = 1; i < N; ++i) if (mu[i])
        for (int j = i, t = binpow(i, i * mu[i]); j < N; j += i)
            h[j] = (LL)h[j] * t % mod;
    for (int i = 1; i < N; ++i)
        h[i] = (LL)h[i - 1] * binpow((LL)binpow(i, g[i]) * h[i] % mod, i) % mod;
    for (int i = 1; i < N; ++i)
        g[i] = (g[i - 1] + (LL)g[i] * i) % (mod - 1);
}
int calc (int n, int m)
{
    int res = 1;
    for (int l = 1, r; l <= n; l = r + 1)
    {
        int a = n / l, b = m / l;
        r = min(n / a, m / b);
        res = (LL)binpow((LL)binpow(f[a], s[b]) * binpow(f[b], s[a]) % mod, g[r] - g[l - 1]) * binpow((LL)h[r] * binpow(h[l - 1]) % mod, (LL)s[a] * s[b] % (mod - 1)) % mod * res % mod;
    }
    return res;
}
int main ()
{
    init();
    int T; read(T); scanf("%*d");
    for (int l, r; T; --T, puts(""))
    {
        read(l, r); --l;
        write(((LL)calc(r, r) * calc(l, l) % mod * binpow(binpow(calc(l, r)), 2) % mod + mod) % mod);
    }
    return 0;
}