HDU 6390 (MultiSchool Round7 Problem 1005)

未分类

---

题意：
已知$f(i,j)=\frac{\phi(ij)}{\phi(i)\phi(j)}$,给定$n,m$,求：$\sum_{i=1}^n\sum_{j=1}^mf(i,j)$.
数据范围$(1\leq n,m \leq 10^6)$.

解析：
先引入几个数论里面常用的变换：
１、$\sum_{d|n}\mu(d)=[n=1]$.
简而言之就是当且仅当$n=1$时$\sum_{d|n}\mu(d)=1$,其他情况均等于$0$.
２、$\sum_{d|n}\phi(d)=n$
$PS:$$\mu(d)$是指$d$的莫比乌斯函数，$\phi(d)$是指$d$的欧拉函数.

回到原先的问题，稍微对$f(i,j)$进行推导：

$$\begin{align*} f(i,j) &=\frac{\phi(ij)}{\phi(i)\phi(j)} \\ &= \frac{gcd(i,j)}{\phi(gcd(i,j))} \end{align*}$$

那么要求的式子就是：

$$\begin{align*} \sum_{i=1}^n\sum_{j=1}^mf(i,j)&=\sum_{i=1}^n\sum_{j=1}^m\frac{gcd(i,j)}{\phi(gcd(i,j))} \\ &= \sum_{d=1}^{min(n,m)} \frac{d}{phi(d)} \sum_{i=1}^{\lfloor n/d\rfloor} \sum_{j=1}^{\lfloor m/d \rfloor}[gcd(i,j)==1] \end{align*}$$

那么现在需要求这么一个东西：

$$\begin{align*} h(n,m) &=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==1] \\ &= \sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}\mu(d) \\ &= \sum_{d=1}^{min(n,m)} \mu(d) \sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor m/d\rfloor} 1 \\ &= \sum_{d=1}^{min(n,m)} \lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d}\rfloor \mu(d) \end{align*}$$

然后两个凑一起就可以求了！中间再加个数论分块，复杂度$emmmm$不会算...