出题人题解 | #小D的Lemon#

原题解链接：https://ac.nowcoder.com/discuss/154293

默认$n\le mn\; \backslash leq\; m$

${\prod }_{i=1}^n{\prod }_{j=1}^{m}g(\gcd (i,j))\backslash prod\_\{i=1\}^\{n\}\; \backslash prod\_\{j=1\}^\{m\}\; g(\backslash operatorname\{gcd\}(i,\; j))$

更换枚举顺序，先枚举$\text{gcd}(i,j)\mathrm{}\backslash text\{gcd\}(i,j)$ ，原式化为

${\prod }_{d=1}^{n}g(d{)}^{{\sum }_{i=1}^n{\sum }_{j=1}^m[\gcd (i,j)=d]}\backslash prod\_\{d=1\}^\{n\}\; g(d)^\{\backslash sum\_\{i=1\}^\{n\}\; \backslash sum\_\{j=1\}^\{m\}[\backslash operatorname\{gcd\}(i,\; j)=d]\}$

将$i,ji,\; j$同时除以$dd$

$={\prod }_{d=1}^{n}g(d{)}^{{\sum }_{i=1}^m{\sum }_{j=1}^m\rfloor }[\gcd (i,j)=1]=\backslash prod\_\{d=1\}^\{n\}\; g(d)^\{\backslash left.\backslash sum\_\{i=1\}^\{m\}\; \backslash sum\_\{j=1\}^\{m\}\backslash right\backslash rfloor\}[\backslash operatorname\{gcd\}(i,\; j)=1]$

$={\prod }_{d=1}^{n}g(d{)}^{{\sum }_{i=1}^{nd}{\sum }_{j=1}^m\rfloor }{\sum }_{ki\lambda kj}\mu (k)=\backslash prod\_\{d=1\}^\{n\}\; g(d)^\{\backslash left.\backslash sum\_\{i=1\}^\{n\; d\}\; \backslash sum\_\{j=1\}^\{m\}\backslash right\backslash rfloor\}\; \backslash sum\_\{k\; i\; \backslash lambda\; k\; j\}\; \backslash mu(k)$

$={\prod }_{d=1}^{n}g(d{)}^{{\sum }_{k=1}^n\mu (k)\lfloor {}_{kd}^n\rfloor \lfloor {}_{kd}^m\rfloor }=\backslash prod\_\{d=1\}^\{n\}\; g(d)^\{\backslash sum\_\{k=1\}^\{n\}\; \backslash mu(k)\backslash left\backslash lfloor\_\{k\; d\}^\{n\}\backslash right\backslash rfloor\backslash left\backslash lfloor\_\{k\; d\}^\{m\}\backslash right\backslash rfloor\}$

设$T=kdT=kd$，则

${\prod }_{T=1}^n{({\prod }_{d\mid T}g(d{)}^{\mu \left(\frac{T}{d}\right)})}^{\lfloor {}_T^n\rfloor \lfloor {}_T^m\rfloor }\backslash prod\_\{T=1\}^\{n\}\backslash left(\backslash prod\_\{d\; \backslash mid\; T\}\; g(d)^\{\backslash mu\backslash left(\backslash frac\{T\}\{d\}\backslash right)\}\backslash right)^\{\backslash left\backslash lfloor\_\{T\}^\{n\}\backslash right\backslash rfloor\backslash left\backslash lfloor\_\{T\}^\{m\}\backslash right\backslash rfloor\}$

设 $F(T)={\prod }_{dT}g(d{)}^{\mu \left(\frac{T}{d}\right)}F(T)=\backslash prod\_\{d\; T\}\; g(d)^\{\backslash mu\backslash left(\backslash frac\{T\}\{d\}\backslash right)\}$

首先筛出 $\mu \backslash mu$ ，然后可以在$O(nlogn)O(nlogn)$的时间内预处理出 $F(T)F(T)$的前缀积

$g(d)\mathrm{}g(d)$ 可以在线性筛的过程中计算

$\lfloor \frac{n}{T}\rfloor \lfloor \frac{m}{T}\rfloor \backslash left\backslash lfloor\backslash frac\{n\}\{T\}\backslash right\backslash rfloor\backslash left\backslash lfloor\backslash frac\{m\}\{T\}\backslash right\backslash rfloor$ 取值有 $O(\sqrt{n})O(\backslash sqrt\{n\})$ 种，所以每次询问可以 $O(\sqrt{n})O(\backslash sqrt\{n\})$ 回答

总复杂度 $O(n\log n+q\sqrt{n})O(n\; \backslash log\; n+q\; \backslash sqrt\{n\})$

#include <bits/stdc++.h>
using namespace std;

typedef long long lo;

const lo mo = 1e9 + 7;
lo t, n, m, cnt, mu[250050], g[250050], inv[250050], f[250050], F[250050], prime[250050];

bool flag[250050];

lo ksm(lo m, lo n)
{
  m = m % mo;
  if (n > 0)
  {
    lo tmp = ksm(m, n / 2);
    if (n & 1) return (((tmp * tmp) % mo) * m) % mo;
    return (tmp * tmp) % mo;
  }
  return 1;
}
int main()
{
  flag[1] = mu[1] = f[1] = F[0] = F[1] = g[1] = inv[1] = 1; lo lin;
  for (int i = 2; i <= 250000; i ++)
  {
    f[i] = 1;
    if (flag[i] == 0)
      prime[++ cnt] = i, mu[i] = -1, g[i] = 1;
    inv[i] = ksm(g[i], mo - 2);
    for (int j = 1; j <= cnt && (lin = prime[j] * i) <= 250000; j ++)
    {
      flag[lin] = 1, g[lin] = g[i] + 1;
      if (i % prime[j] == 0)
      {
        mu[lin] = 0; break;
      }
      mu[lin] = - mu[i];
    }
  }
  for (int i = 1; i <= 250000; i ++)
  {
    if (mu[i] != 0)
      for (int j = i; j <= 250000; j += i)
        f[j] = f[j] * ((mu[i] == 1) ? g[j / i] : inv[j / i]) % mo;
    F[i] = F[i - 1] * f[i] % mo;
  }
  scanf("%lld", &t);
  while (t --)
  {
    lo ans = 1; scanf("%lld%lld", &n, &m); lin = 0;
    if (n > m)
      swap(n, m);
    for (int i = 1; i <= n; i = lin + 1)
    {
      lin = min(n / (n / i), m / (m / i));
      lo pre = F[lin] * ksm(F[i - 1], mo - 2) % mo;
      ans = ans * ksm(pre, (n / i) * (m / i)) % mo;
    }
    printf("%lld\n", ans);
  }
  return 0;
}