P7486 题解

· · 题解

骗你的，其实根本不需要二维前缀积或者离散对数之类的玩意，这里给出一个小常数大力莫反的做法，不加快读轻松最优解第二。

首先 \operatorname{lcm}(i,j)=\dfrac{ij}{\gcd(i,j)}，那么暴力带进去有

\prod\limits_{l \le i,j \le r} \operatorname{lcm}(i,j)^{\operatorname{lcm}(i,j)}=\prod\limits_{l \le i,j \le r} \left( \dfrac{ij}{\gcd(i,j)} \right)^{\frac{ij}{\gcd(i,j)}}

把指数分到分子分母上有

\prod_{l \le i,j \le r} \dfrac{ij^{\frac{ij}{\gcd(i,j)}}}{\gcd(i,j)^{\frac{ij}{\gcd(i,j)}}}

然后套路的先枚举 d=\gcd(i,j)，方便表示，记 L_d=\left\lceil \dfrac ld \right \rceil，R_d=\left \lfloor \dfrac rd \right \rfloor，则原式变为

\prod\limits_{d=1}^r \prod\limits_{i=L_d}^{R_d} \prod\limits_{j=L_d}^{R_d} [\gcd(i,j)=1]\dfrac{d^{2ijd} \cdot i^{ijd} \cdot j^{ijd}}{d^{ijd}}

约一下分有

\prod\limits_{d=1}^r \prod\limits_{i=L_d}^{R_d} \prod\limits_{j=L_d}^{R_d} [\gcd(i,j)=1] (ijd)^{ijd}

然后考虑莫反，即

\prod\limits_{d=1}^r \prod\limits_{i=L_d}^{R_d} \prod\limits_{j=L_d}^{R_d} (ijd)^{ijd} \sum\limits_{k \mid \gcd(i,j)} \mu(k)

套路的先枚举 k，重记 L_d= \left \lceil \dfrac l{dk} \right \rceil，R_d=\left \lfloor \dfrac r{dk} \right \rfloor，则提出来变成

\prod\limits_{d=1}^r \prod\limits_{k=1}^{R_d} \mu(k) \left[ \prod\limits_{i=L_d}^{R_d} \prod\limits_{j=L_d}^{R_d} (ijdk^2)^{ijdk^2} \right]^{\mu(k)}

你把里面的东西放开，做到目前你发现 \prod\limits_{i=l}^r i^i 这种东西出现了一万次，记为 f(l,r)，然后记 \sum\limits_{s=L_d}^{R_d} s 为 S_d，则把中括号里面的东西放开变成

\prod\limits_{d=1}^r \prod\limits_{k=1}^{\left\lfloor l/d \right \rfloor} (dk^2)^{dk^2S_d^2} f(l,r)^{2dk^2S_d^2}

你分别把两个东西指数上的分贡献算出来即可，可以做到 \mathcal O(Tn \log n)，这个东西只有 60。

考虑优化，注意到 dk 的成分很高，记 m=dk，重记 f(t)=\prod\limits_{s=1}^t s，原式变为

\prod\limits_{m=1}^r \prod\limits_{k \mid m} \left[ (mk)^{mkS_m^2} \left( \dfrac{f(R_m)}{f(L_m-1)} \right)^{2mkS_m} \right]^{\mu(k)}

考虑前面那一半东西的贡献，即

\prod\limits_{k \mid m} (mk)^{mkS_m^2\mu(k)}

分 m 和 k 拆开化简之后就是

m^{mS_m^2 \sum\limits_{k \mid m} k \mu(k)} \left( \prod\limits_{k \mid m} k^{k \mu(k)} \right)^{mS_m^2}

观察指数的公共部分，考虑 F(m)=m^{\sum\limits_{k \mid m} k\mu(k)} \prod\limits_{k \mid m} k^{k \mu(k)}，则原式就是

\prod\limits_{m=1}^r F^{mS(m)}(m) \cdot \left[ \dfrac{f(R_m)}{f(L_m-1)} \right]^{2mkS_m \prod\limits_{k \mid m} k^k \mu(k)}

预处理 \prod\limits_{k \mid m} k^k \mu(k) 和 F(m) 的前缀和然后对这玩意整除分块即可。

总时间复杂度 \mathcal O(n \log nM+t\sqrt r\log M)，其中 M 为模数，其实复杂度是一样的，但是常数很小。

::::success[code]

constexpr int Mod = 32465177;
constexpr int Maxn = 1e6 + 5;

inline void Add(int &x, int y, int mod) { x += y; if (x >= mod) x -= mod; }
inline void Sub(int &x, int y, int mod) { x -= y; if (x < 0) x += mod; }
inline void Mul(int &x, int y, int mod) { x = 1ll * x * y % mod; }

inline int binpow(int a, int b) {
  if (b < 0) b = (b % (Mod - 1) + Mod - 1) % (Mod - 1);
  int res = 1;
  while (b) {
    if (b & 1) Mul(res, a, Mod);
    Mul(a, a, Mod), b >>= 1;
  }
  return res;
}

int mu[Maxn], g[Maxn];
int cnt, prime[Maxn];
bitset <Maxn> vis;

int h[Maxn], f[Maxn], rec[Maxn];
int invh[Maxn], invf[Maxn];
int preh[Maxn];

void init(int lim) {
  mu[1] = g[1] = 1;
  for (int i = 2; i <= lim; i++) {
    if (!vis[i]) {
      prime[++cnt] = i;
      mu[i] = -1, g[i] = (Mod - i) % (Mod - 1);
    }
    for (int j = 1; j <= cnt && i * prime[j] <= lim; j++) {
      vis[i * prime[j]] = true;
      if (i % prime[j]) {
        mu[i * prime[j]] = -mu[i];
        g[i * prime[j]] = 1ll * g[i] * g[prime[j]] % (Mod - 1);
      } else {
        mu[i * prime[j]] = 0;
        g[i * prime[j]] = g[i];
        break;
      }
    }
  }
  for (int i = 0; i <= lim; i++) h[i] = 1;
  for (int i = 1; i <= lim; i++) {
    // h[i] = 1;
    if (!mu[i]) continue;
    int val = binpow(i, (i * mu[i] + Mod - 1) % (Mod - 1));
    for (int m = i; m <= lim; m += i) Mul(h[m], val, Mod);
  }
  for (int m = 1; m <= lim; m++) {
    Mul(h[m], binpow(m, g[m]), Mod);
  }
  for (int m = 1; m <= lim; m++) {
    h[m] = binpow(h[m], m);
    Mul(h[m], h[m - 1], Mod);
  }
  for (int m = 1; m <= lim; m++) {
    Mul(g[m], m, Mod - 1);
    Add(g[m], g[m - 1], Mod - 1);
  }
  f[0] = 1;
  for (int m = 1; m <= lim; m++) {
    f[m] = 1;
    Mul(f[m], f[m - 1], Mod);
    Mul(f[m], binpow(m, m), Mod);
  }
  rec[1] = h[1]; rec[0] = 1;
  for (int m = 2; m <= lim; m++) {
    rec[m] = 1ll * rec[m - 1] * h[m] % Mod; 
  }
  int inv = binpow(rec[lim], Mod - 2);
  for (int m = lim; ~m; m--) {
    invh[m] = 1ll * inv * (m ? rec[m - 1] : 1) % Mod;
    Mul(inv, h[m], Mod);
  }
  rec[1] = f[1]; rec[0] = 1;
  for (int m = 2; m <= lim; m++) {
    rec[m] = 1ll * rec[m - 1] * f[m] % Mod;
  }
  inv = binpow(rec[lim], Mod - 2);
  for (int m = lim; ~m; m--) {
    invf[m] = 1ll * inv * (m ? rec[m - 1] : 1) % Mod;
    Mul(inv, f[m], Mod);
  }
}

void Main() {
  int ql, qr; cin >> ql >> qr;
  int ans = 1;
  for (int l = 1, r; l <= qr; l = r + 1) {
    int ul = (ql + l - 1) / l, ur = qr / l;
    r = min(qr / ur, (ul > 1) ? (ql - 1) / (ul - 1) : qr);
    if (ul > ur) continue;
    int S = 1ll * (ul + ur) * (ur - ul + 1) / 2 % (Mod - 1);
    Mul(ans, binpow(1ll * h[r] * invh[l - 1] % Mod, 1ll * S * S % (Mod - 1)), Mod);
    Mul(ans, binpow(1ll * f[ur] * invf[ul - 1] % Mod, 1ll * 2 * S % (Mod - 1) * (g[r] - g[l - 1] + Mod - 1) % (Mod - 1)), Mod);
  }
  cout << ans << '\n';
}

::::

::::info[AI 使用说明] 作者把思路丢给 AI 生成代码并用小号提交验证了正确性。 ::::