P7486 「Stoi2031」彩虹

· · 题解

P7486 「Stoi2031」彩虹

令 S(a,b)=\prod\limits_{i=1}^{a}\prod\limits_{j=1}^{b}\operatorname{lcm}(a,b)^{\operatorname{lcm}(a,b)}。

求：

\frac{S(r,r)\times S(l-1,l-1)}{S(r,l-1)\times S(l-1,r)}

不妨设 a \leq b。

令 dp=t，则有：

\begin{aligned} S(a,b)&=\prod\limits_{i=1}^{a}\prod\limits_{j=1}^{b}\operatorname{lcm}(a,b)^{\operatorname{lcm}(a,b)}\\ &=\prod_{i=1}^{a}\prod_{j=1}^{b}\frac{ij}{\gcd(a,b)}^{(\frac{ij}{\gcd(a,b)})}\\ &=\prod_{d=1}^{a}\prod_{i=1}^{a}\prod_{j=1}^{b}\frac{ij}{d}^{(\frac{ij}{d})[\gcd(i,j)=d]}\\ &=\prod_{d=1}^{a}\prod_{i=1}^{\lfloor\frac{a}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{b}{d}\rfloor}(ijd)^{ijd[\gcd(i,j)=1]}\\ &=\prod_{d=1}^{a}\prod_{i=1}^{\lfloor\frac{a}{d}\rfloor}\prod_{j=1}^{\lfloor\frac{b}{d}\rfloor}(ijd)^{ijd\sum\limits_{p=1}^{\lfloor\frac{a}{d}\rfloor}\mu(p)[p|i][p|j]}\\ &=\prod_{d=1}^{a}\prod_{p=1}^{\lfloor\frac{a}{d}\rfloor}\prod_{i=1}^{\lfloor\frac{a}{d}\rfloor}[p|i]\prod_{j=1}^{\lfloor\frac{b}{d}\rfloor}[p|j](ijd)^{ijd\mu(p)}\\ &=\prod_{d=1}^{a}\prod_{p=1}^{\lfloor\frac{a}{d}\rfloor}\prod_{i=1}^{\lfloor\frac{a}{dp}\rfloor}\prod_{j=1}^{\lfloor\frac{b}{dp}\rfloor}(ijdp^2)^{ijdp^2\mu(p)}\\ &=\prod_{t=1}^{a}\prod_{p|t}\prod_{i=1}^{\lfloor\frac{a}{t}\rfloor}\prod_{j=1}^{\lfloor\frac{b}{t}\rfloor}(ijtp)^{ijtp\mu(p)}\\ \end{aligned}

令 s(x)=\sum\limits_{i=1}^{x}i=\frac{x(x+1)}{2}，f(x)=\prod\limits_{i=1}^{x}i^i，则有：

\prod_{i=1}^{n}\prod_{j=1}^{m}(ij)^{ij}=f(n)^{s(m)}\times f(m)^{s(n)}

令其为 G(n,m)。

另有：

\prod_{i=1}^{n}\prod_{j=1}^{m}(tp)^{ij}=(tp)^{s(n)\times S(m)}

带回原式有：

\prod_{t=1}^{a}\left( \prod_{p|t}\left( G(\lfloor\frac{a}{t}\rfloor,\lfloor\frac{b}{t}\rfloor) \times (tp)^{s(\lfloor\frac{a}{t}\rfloor)\times s(\lfloor\frac{b}{t}\rfloor)} \right)^{p\mu(p)} \right)^{t}

另 h(x)=\sum\limits_{d|x}d\mu(d),y(x)=\prod\limits_{d|x}d^{d\mu(d)}，则有：

\prod_{t=1}^{a}G(\lfloor\frac{a}{t}\rfloor,\lfloor\frac{b}{t}\rfloor)^{t \cdot h(t)}\times (t^{h(t)}\times y(t))^{t\times s(\lfloor\frac{a}{t}\rfloor)\times s(\lfloor\frac{b}{t}\rfloor)}

再令 hh(x)=x\times h(x),yy(x)=(x^{h(x)}\times y(x))^{x}，可得：

\prod_{t=1}^{a}G(\lfloor\frac{a}{t}\rfloor,\lfloor\frac{b}{t}\rfloor)^{hh(t)}\times yy(t)^{s(\lfloor\frac{a}{t}\rfloor)\times s(\lfloor\frac{b}{t}\rfloor)}

最后前缀和 \text{+} 前缀积 \text{+} 数论分块即可。

再加一个小优化，设一个阈值 S，对于 1 \leq t < S 的直接暴力算，因为这部分 l,r 相差较小。

对于 S \leq t \leq n 的，再数论分块算。

#include <bits/stdc++.h>

using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

inline void write(int x)
{
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

const int _ = 1e6 + 7, mod = 32465177;

bool vis[_];

int cnt, pr[_], mu[_], f[_], h[_], y[_];

int ksm(int x, int y)
{
    int res = 1;
    while(y)
    {
        if(y & 1) res = 1ll * res * x % mod;
        x = 1ll * x * x % mod;
        y >>= 1;
    }
    return res;
}

void init()
{
    mu[1] = 1;
    f[1] = 1;
    y[1] = 1;
    for(int i = 2; i <= _ - 7; ++i)
    {
        f[i] = 1ll * f[i - 1] * ksm(i, i) % mod;
        y[i] = 1;
        if(!vis[i])
        {
            pr[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= cnt && i * pr[j] <= _ - 7; ++j)
        {
            int p = i * pr[j];
            vis[p] = 1;
            if(i % pr[j] == 0)
            {
                mu[p] = 0;
                break;
            }
            mu[p] = -mu[i];
        }
    }
    for(int i = 1; i <= _ - 7; ++i)
        for(int j = 1; i * j <= _ - 7; ++j)
        {
            h[i * j] = ((h[i * j] + mu[i] * i) % (mod - 1) + (mod - 1)) % (mod - 1);
            y[i * j] = 1ll * y[i * j] * ksm(i, i * mu[i] + mod - 1) % mod;
        }
    for(int i = 1; i <= _ - 7; ++i)
    {
        y[i] = ksm(1ll * ksm(i, h[i]) * y[i] % mod, i);
        h[i] = 1ll * h[i] * i % (mod - 1);
    }
    y[0] = 1;
    for(int i = 2; i <= _ - 7; ++i)
    {
        y[i] = 1ll * y[i - 1] * y[i] % mod;
        h[i] = (h[i] + h[i - 1]) % (mod - 1);
    }
}

int s(int x)
{
    return 1ll * x * (x + 1) / 2 % (mod - 1);
}

int g(int x, int y)
{
    return 1ll * ksm(f[x], s(y)) * ksm(f[y], s(x)) % mod;
}

int hh(int l, int r)
{
    return ((h[r] - h[l - 1]) % (mod - 1) + (mod - 1)) % (mod - 1);
}

int yy(int l, int r)
{
    return 1ll * y[r] * ksm(y[l - 1], mod - 2) % mod;
}

int S(int a, int b)
{
    if(a > b) swap(a, b);
    int res = 1;
    for(int i = 1, j; i <= a; i = j + 1)
    {
        j = min(a / (a / i), b / (b / i));
        res = 1ll * res * ksm(g(a / i, b / i), hh(i, j)) % mod * ksm(yy(i, j), 1ll * s(a / i) * s(b / i) % (mod - 1)) % mod; 
    }
    return res;
}

int solve(int l, int r)
{
    swap(l, r);
    int ans1 = 1ll * S(r, r) * S(l - 1, l - 1) % mod, ans2 = 1ll * S(r, l - 1) * S(l - 1, r) % mod;
    return 1ll * ans1 * ksm(ans2, mod - 2) % mod;
}

signed main()
{
    init();
    int t = read(), n = read();
    while(t--)
    {
        write(solve(read(), read()));
        putchar('\n');
    }
}