P7486 「Stoi2031」彩虹

P7486 「Stoi2031」彩虹

$$\begin{array}{rl}\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 }(ijd{k}^2{)}^{ijd{k}^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{array}$$

记 $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;
}