欧拉函数表示从 11 到 nn 中与 xx 互质的数的个数。

φ(n)=∑k=1n[gcd⁡(k,n)=1]=n∏p∣n(1−1p),\varphi(n) = \sum_{k=1}^{n} [\gcd(k,n)=1] = n \prod_{p\mid n} \left(1-\frac{1}{p}\right),

其中 pp 取遍 nn 的所有不同质因子。

性质

是积性函数，若 gcd⁡(m,n)=1\gcd(m,n)=1，则 φ(mn)=φ(m)φ(n)\varphi(mn)=\varphi(m)\varphi(n)。

∑d∣nφ(d)=n\sum_{d\mid n} \varphi(d) = n

计算方法

若 n=p1a1⋯pkakn=p_1^{a_1}\cdots p_k^{a_k}，则 φ(n)=n(1−1p1)⋯(1−1pk)\varphi(n)=n\left(1-\frac1{p_1}\right)\cdots\left(1-\frac1{p_k}\right)。

P2303 [SDOI2012] Longge 的问题

P2303 [SDOI2012] Longge 的问题。

∑i=1ngcd⁡(i,n)=∑j∣nj⋅φ(nj)\begin{aligned} \sum_{i=1}^n \gcd(i,n) = \sum_{j \mid n} j \cdot \varphi(\frac{n}{j}) \end{aligned}

到这里已经够了，下面是题解的优化：

=∑j∣nnjφ(j)=∑j∣nnj(j⋅∏p∣jp−1p)=n∑j∣n∏p∣jp−1p\begin{aligned} &= \sum_{j \mid n} \frac{n}{j} \varphi(j) \\ &= \sum_{j \mid n} \frac{n}{j} ( j \cdot \prod_{p \mid j} \frac{p - 1}{p} ) \\ &= n \sum_{j \mid n} \prod_{p | j} \frac{p - 1}{p} \end{aligned}

n=p1b1p2b2p3b3⋯pkbkn = p_1^{b_1} p_2^{b_2} p_3^{b_3} \cdots p_k^{b_k}

=n∏i=1kbipi−bi+pipi=n \prod_{i = 1}^{k} \frac{b_i p_i - b_i + p_i}{p_i}