题解：P13645 Totient with Divisors
Feather_Moon
·
·
题解
题目传送门
题意
给你多组询问，求：
\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)\sigma(ij)
其中 1\leq T,n,m\leq 10^5。
分析
不妨设 n \leq m。
首先我们肯定要把 \sigma(ij) 拆开。
然后这里有一个结论：
\sigma(ij)=\sum_{x\mid i}\sum_{y\mid j}\dfrac{iy}{x}[\gcd(x,y)=1]
::::success[该结论的简要证明]
:::info[感性证明]{open}
我们有:
\sigma(x)=\prod_{i}(1+p_i+p_i^2+\cdots+p_i^{a_i})
每个质因子可以独立处理。
$\gcd(x,y)=1$ 保证了每个质因子 $x$ 和 $y$ 中有一个指数为 $0$。
那么 $\dfrac{iy}{x}$ 就可以取到一个质因子在 $ij$ 中的所有指数。
:::
:::info[理性证明]{open}
$$\sigma(x)=\prod_{i}(1+p_i+p_i^2+\cdots+p_i^{a_i})
$$
考虑每个质因子 $p$ 独立处理。
令 $v_p(n)$ 表示质因子 $p$ 整除 $n$ 的最高幂次。
由 $x\mid i,y\mid j$ 易得 $0 \leq v_p(x) \leq v_p(i),0 \leq v_p(y) \leq v_p(j)$。
由 $\gcd(x,y)=1$，易得 $ \min(v_p(x),v_p(y))=v_p(1)=0$。
- 当 $v_p(x)=0$ 且 $v_p(y) \neq 0$ 时，$v_p(\dfrac{iy}{x})=v_p(i)+v_p(y)$，恰好取得 $[v_p(i)+1,v_p(i)+v_p(j)=v_p(ij)]$ 每个数各一次。
- 当 $v_p(y)=0$ 时，$v_p(\dfrac{iy}{x})=v_p(i)-v_p(x)$，恰好取得 $[0,v_p(i)]$ 每个数各一次。
故 $v_p(\dfrac{iy}{x})$ 不重不漏的取了 $[0,v_p(ij)]$ 每个数各一次。
而所有质因子的每种组合都会被取一遍，故结论成立。
:::
::::
~~最难点已过，恭喜你切掉一道黑题。~~
接下来就是我们喜闻乐见的推式子时间：
$$\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)\sigma(ij)$$
用上述结论把 $\sigma(ij)$ 替掉，得：
$$\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)\sum_{x\mid i}\sum_{y\mid j}\dfrac{iy}{x}[\gcd(x,y)=1]$$
经典的拆 $\gcd$：
$$
\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)\sum_{x\mid i}\sum_{y\mid j}\dfrac{iy}{x}\sum_{d\mid \gcd(x,y)}\mu(d)
$$
交换求和顺序，把 $d$ 外提：
$$
\sum_{d=1}^n \mu(d)(\sum_{d \mid x}^n\sum_{x\mid i}^n \dfrac{i\varphi(i)}{x})(\sum_{d\mid y}^m y\sum_{y \mid j}^m\varphi(j))
$$
令 $x=dX,i=xI,y=dY,j=yJ$：
$$
\sum_{d=1}^n \mu(d)(\sum_{X=1}^{\lfloor n/d \rfloor}\sum_{I=1}^{\lfloor n/dX \rfloor}I\varphi(dXI))(\sum_{Y=1}^{\lfloor m/d \rfloor} dY\sum_{J=1}^{\lfloor m/dY \rfloor}\varphi(dYJ))
$$
把 $dY$ 中的 $d$ 往外提，交换 $J,Y$ 的求和顺序：
$$
\sum_{d=1}^{n}d\mu(d)(\sum_{X=1}^{\lfloor n/d \rfloor}\sum_{I=1}^{\lfloor n/dX \rfloor}I\varphi(dXI))(\sum_{J=1}^{\lfloor m/d \rfloor}\sum_{Y=1}^{\lfloor m/dJ \rfloor}Y\varphi(dJY))
$$
注意两个括号是相同的形式，我们令：
$$
F(x,y)=\sum_{i=1}^x\sum_{j=1}^{\lfloor x/i \rfloor}j\varphi(ijy)
$$
令 $T=ij$：
$$
\begin{aligned}
F(x,y)&=\sum_{T=1}^x\varphi(Ty)\sum_{j \mid T}j\\
&=\sum_{T=1}^x\varphi(Ty)\sigma(T)\\
\end{aligned}
$$
注意到这东西可以递推：
$$
F(x,y)=F(x-1,y)+\varphi(xy)\sigma(x)
$$
将其带入原式，得：
$$
\sum_{d=1}^nd\mu(d) F(\lfloor \dfrac{n}{d} \rfloor,d) F(\lfloor \dfrac{m}{d} \rfloor,d)
$$
然后就可以用类似 [P4240](https://www.luogu.com.cn/problem/P4240) 的方法做了！具体的说：
然后你会发现这个时候 $F$ 里面是带 $d$ 的不能直接的数论分块。我们考虑平衡。
套路地，我们把整个式子换元换出来。我们令：
$$
G(n,m,k)=\sum_{d=1}^kd\mu(d) F(\lfloor \dfrac{n}{d} \rfloor,d) F(\lfloor \dfrac{m}{d} \rfloor,d)
$$
然后我们发现当 $d$ 很大的时候 $\lfloor \dfrac{n}{d} \rfloor,\lfloor \dfrac{m}{d} \rfloor$ 很小，这是不是意味着我们可以预处理一部分 $G$？
首先我们可以用递推把所有的 $F$ 给预处理出来，时间复杂度是调和级数级别的即 $\mathcal{O}(n \ln n)$ 的。
设置一个阈值 $S$，$\lfloor \dfrac{n}{d} \rfloor \leq S$ 的部分预处理。用人话说，我们要把 $G(x,y,z)$ 中 $x \leq S$ 的所有 $G(x,y,z)$ 的值预处理出来。
因为第三维是可以递推 $\mathcal{O}(1)$ 求的，$x$ 有 $S$ 种取值，$y \times z \leq m$，预处理的时间复杂度是 $\mathcal{O}(mS)$ 的。
接下来我们就可以数论分块了，如果预处理过了数论分块算复杂度是 $\mathcal{O}(T \sqrt{n})$ 的，没预处理过暴力算。因为我们已经把 $\lfloor \dfrac{n}{d} \rfloor \leq S$ 的部分预处理了，所以剩下没预处理的一定满足 $d\le \lfloor\dfrac{n}{S+1}\rfloor$，时间复杂度为 $\mathcal{O}(\dfrac{nT}{S})$。
总时间复杂度 $\mathcal{O}(\dfrac{nT}{S}+T \sqrt{n}+mS+n \ln n)$。反正 $n,m$ 同阶，$S$ 取 $\sqrt{T}$ 可以达到时间复杂度 $O((n+m)\sqrt{T}+T\sqrt{n}+n \ln n)$。
::::success[代码]
~~代码写的就是一坨大家不要拿我的代码做参考~~
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,L=405,TT=998244353;
int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
void write(int x){
if(x<0)x=-x,putchar('-');
if(x>9)write(x/10);
putchar(x%10+'0');
}
int pri[N],top;
int flg[N];
int mu[N],phi[N];
long long d[N],sp[N];
void init(int n){
mu[1]=1;phi[1]=1;d[1]=1;
for(int i=2;i<=n;i++){
if(!flg[i]){
pri[++top]=i;
phi[i]=i-1;
mu[i]=-1;
d[i]=i+1;
sp[i]=i+1;
}
for(int j=1;j<=top;j++){
int pri_j=pri[j];
if(i*pri_j > n)break;
flg[i*pri_j]=1;
if(i%pri_j==0){
sp[i*pri_j]=sp[i]*pri_j+1;
d[i*pri_j]=d[i]/sp[i]*sp[i*pri_j];
phi[i*pri_j]=phi[i]*pri_j;
mu[i*pri_j]=0;
break;
}
phi[pri_j*i]=phi[i]*phi[pri_j];
d[pri_j*i]=d[pri_j]*d[i];
mu[i*pri_j]=-mu[i];
sp[i*pri_j]=1+pri_j;
}
}
for(int i=1;i<=n;i++)d[i]=d[i]%TT;
}//筛
int T,n,m;
int S;
int f[L][N];
int af[N][505];
void make_f(){
for(int i=1;i<=S;i++){
for(int j=1;i*j<=(N-5);j++){
f[i][j]=((long long)f[i-1][j]+((long long)phi[i*j]*d[i]%TT))%TT;
}
}
for(int j=1;j<=(N-5)/S;j++){//注意是 N/S 不是 S
for(int i=1;i*j<=(N-5);i++){
af[i][j]=((long long)af[i-1][j]+((long long)phi[i*j]*d[i]%TT))%TT;
}
}
}//预处理 f，懒得用 vector 所以我用了静态数组
vector<int> g[L][L];
int now;
void make_g(){
for(int i=1;i<=S;i++){
for(int j=1;j<=S;j++){
g[i][j].push_back(0);
for(int k=1;i*k<=(N-5) && j*k<=(N-5);k++){
g[i][j].push_back(((long long)g[i][j][k-1]+(long long)k*(long long)mu[k]%TT*(long long)f[i][k]%TT*f[j][k]%TT+TT)%TT);
}
}
}
}//预处理 g
int calc(int n,int m){
int ret=0,l=1,r=0;
while(l<=n){
r=min(n/(int)(n/l),m/(int)(m/l));
if(r>n)r=n;
if((n/l)<=S && (m/l)<=S){
ret=((long long)ret+(long long)g[n/l][m/l][r]-g[n/l][m/l][l-1]+TT)%TT;
}else{
for(int k=l;k<=r;k++)ret=((long long)ret+(long long)k*(long long)mu[k]%TT*(long long)af[n/l][k]%TT*af[m/l][k]%TT+TT)%TT;
//暴力计算
}
l=r+1;
}
return ret;
}
signed main(){
T=read();S=200;
init(N-5);
make_f();make_g();
while(T--){
n=read(),m=read();
if(n>m)swap(n,m);
write(calc(n,m));putchar('\n');
}
return 0;
}
```
::::
## 后记
为出题喜欢用经典结论的出题人献上由衷的祝福。
~~我劝你们家里多备几个【数据删除】。~~