题解[P8570 牵连的世界]

· · 题解

原题链接

题意： 给定 n,m\leq 5\times 10^5，求 \displaystyle \left(\sum_{i=1}^n\sum_{j=1}^md(ij)\varphi(ij)\right)\bmod 10^9+7。

不妨设 n\leq m。

\sum_{i=1}^n\sum_{j=1}^md(ij)\varphi(ij) =\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^md(ij)\dfrac{\varphi(i)\varphi(j)}{\varphi(d)}d[\gcd(i,j)=d] =\sum_{d=1}^n\dfrac{d}{\varphi(d)}\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}d(ijd^2)\varphi(id)\varphi(jd)\sum_{k|i,k|j}\mu(k) =\sum_{T=1}^n\left(\sum_{d|T}\dfrac{d}{\varphi(d)}\mu(T/d)\right)\sum_{i=1}^{n/T}\sum_{j=1}^{m/T}d(ijT^2)\varphi(iT)\varphi(jT)

设 \displaystyle f(T)=\sum_{d|T}\dfrac{d}{\varphi(d)}\mu(T/d)，然后把后面的因数个数拆开。

=\sum_{T=1}^nf(T)\sum_{T|i,1\leq i\leq n}\sum_{T|j,1\leq j\leq m}\varphi(i)\varphi(j)d(ij) =\sum_{T=1}^nf(T)\sum_{T|i,1\leq i\leq n}\sum_{T|j,1\leq j\leq m}\varphi(i)\varphi(j)\sum_{a|i}\sum_{b|j}[\gcd(a,b)=1] =\sum_{T=1}^nf(T)\sum_{T|i,1\leq i\leq n}\sum_{T|j,1\leq j\leq m}\varphi(i)\varphi(j)\sum_{a|i}\sum_{b|j}\sum_{t|a,t|b}\mu(t) =\sum_{T=1}^nf(T)\sum_{T|i,1\leq i\leq n}\sum_{T|j,1\leq j\leq m}\varphi(i)\varphi(j)\sum_{t|i,t|j}\mu(t)d(i/t)d(j/t)

由于 t|i,T|i 等价于 \operatorname{lcm}(t,T)|i，枚举 x=\operatorname{lcm}(t,T)。

\sum_{t=1}^n\mu(t)\sum_{t|x,1\leq x\leq n}\left(\sum_{x|i,1\leq i\leq n}\varphi(i)d(i/t)\right)\left(\sum_{x|j,1\leq j\leq m}\varphi(j)d(j/t)\right)\sum_{T=1}^nf(T)[\operatorname{lcm}(t,T)=x]

直接枚举 t 及 t|x，再枚举 x|i 的复杂度是：

\sum\limits_{t=1}^n\sum\limits_{i=1}^{n/x}n/(xi)=\sum\limits_{t=1}^nn/x\ln(n/x)=O(n\ln^2 n)

所以只需对 t,x 快速求出 \displaystyle \sum_{T=1}^nf(T)[\operatorname{lcm}(t,T)=x]。

但其实我们只需对 \mu(t) 非零的 t 求值。

再观察一下 f(T)=\sum\limits_{d|T}\dfrac{d}{\varphi(d)}\mu(T/d)，这显然是积性的。

而 f(p^k)=\begin{cases}-1+\dfrac{p}{p-1}=\dfrac{1}{p-1},&k=1\\ \dfrac{p^k}{\varphi(p^k)}-\dfrac{p^{k-1}}{\varphi(p^{k-1})}=0,&k\geq 2\end{cases}，也即 f(T) 仅在 \mu(T) 非零时有值。

既然 \mu(t)\neq 0,\mu(T)\neq 0,x=\operatorname{lcm}(t,T)，则 \mu(x)\neq0。

所以我们只需要没有平方因子的 t,T,x，求出 \displaystyle \sum_{T=1}^nf(T)[\operatorname{lcm}(t,T)=x]。

设 x,t,T 的质因子集合分别为 P_x,P_t,P_T，则 P_t\cup P_T=P_x 且条件充要。

所以 P_T 必由 P_x\setminus P_t 的全部元素与 P_t 的一部分拼成。

因此 \displaystyle \sum_{T=1}^nf(T)[\operatorname{lcm}(t,T)=x]=\left(\prod_{p\in P_x,p\not\in P_t}f(p)\right)\left(\prod_{p\in P_t}\left(f(p)+1\right)\right)。

最后面的 +1 就相当于 P_t 中的元素可选可不选。

另设积性函数 g(p)=f(p)+1=\dfrac{p}{p-1},g(n)=\prod\limits_{p|n}\dfrac{p}{p-1}。

则 \displaystyle \sum_{T=1}^nf(T)[\operatorname{lcm}(t,T)=x]=f(x/t)g(t)。

线性预处理出 f,g,d,\varphi,\mu，便可 O(n\ln^2 n) 做完了，空间线性。

核心代码： 

for(t=1;t<=n;++t)if(mu[t]){
  res=0;
  for(x=t;x<=n;x+=t)if(mu[x]){
    sn=sm=0;
    for(i=x;i<=n;i+=x)add(sn,phi[i]*d[i/t]);
    for(i=x;i<=m;i+=x)add(sm,phi[i]*d[i/t]);
    add(res,1ll*sn*sm%mod*f[x/t]%mod*g[t]%mod);
  }
  add(ans,1ll*res*(mu[t]+mod)%mod);
}

评测记录 为什么时限不开 100ms。

但再仔细观察一下，把每次处理的 t 的倍数拉出来，

我们发现在对于 t|x 的 x 做的事无非是一个整除的后缀和。

因为在 t|x,t|i 时，x|i\Leftrightarrow \frac{x}{t}|\frac{i}{t}。

所以这部分能被一个 \text{Dirichlet} 后缀和优化掉。

总时间复杂度降至 O(n\ln n\ln\ln n)，虽然在数据范围只有 5\times 10^5 时没太大区别。

核心代码：

for(t=1;t<=n;++t)if(mu[t]){
  res=0;
  for(i=t;i<=n;i+=t)sn[i/t]=phi[i]*d[i/t];
  for(j=t;j<=m;j+=t)sm[j/t]=phi[j]*d[j/t];
  for(nn=n/t,k=1;k<=prm&&p[k]<=nn;++k)
    for(l=nn/p[k];l;--l)add(sn[l],sn[l*p[k]]);
  for(nn=m/t,k=1;k<=prm&&p[k]<=nn;++k)
    for(l=nn/p[k];l;--l)add(sm[l],sm[l*p[k]]);
  for(x=t;x<=n;x+=t)if(mu[x])
    add(res,1ll*sn[x/t]*sm[x/t]%mod*f[x/t]%mod*g[t]%mod);
  add(ans,1ll*res*(mu[t]+mod)%mod);
}

为什么数据范围不加个0。