自动搬运

查看原文

来自洛谷，原作者为

	Y_B_X ...

搬运于2025-08-24 22:40:15，当前版本为作者最后更新于2022-10-05 23:02:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

原题链接

题意： 给定 $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。