果果要求掌握的东西当然是要掌握的咯。
最终形式
$$
\Large{n=\sum_{d|n}^{}}{\varphi(d)}
$$
证明
$$
\large\because n=\sum_{d|n}\sum_{j=1}^{n}{[\gcd(j,n)=d]}
$$
解释一下，首先，这里的 $\gcd(j,n)$ 一定是只有一个值，不可能说有两个不同的值来自同一个 $\gcd(j,n)$ ；其次，为什么这一坨东西等于 $n$ 呢，因为其一说的每个 $\gcd$ 都有唯一确定的值，因此我们只需要枚举 $\gcd$ 的每种可能并枚举所有 $n$ 以内的正整数就必然有且仅有一种可能的 $d$ 满足每组 $\gcd(j,n)=d$ 。
换句话说，因为一个 $\gcd(j,n)$ 只对应唯一一个 $d$ ，这里我们把所有可能的 $\gcd$ 的值和所有的 j 都枚举了自然其值也就等于 $n$ 了（主要就是说明一个不重也不漏）。
$$
\large\therefore \ n=\sum_{d|n}\sum_{j=1}^{\frac{n}{d}}{[\gcd(j,\frac{n}{d})=1]}
$$
这里没什么好说的，目的是把 $\gcd$ 的值化为 $1$ 后能转化成欧拉函数的形式。
$$
\large\therefore n=\sum_{d|n}{\varphi(\frac{n}{d})}
$$
$$
\large\therefore n=\sum_{d|n}{\varphi(d)}
$$
这里是因为每个 $\frac{n}{d}$ 和 $d$ 是对应的，所以能如此转化。
例题
- 多组数据，每组数据给出一个数 $n$ ，求 $\sum_{i=1}^{n}{\gcd(i,n)}$ 。
利用欧拉反演，改变题目公式如下：
$$
\sum_{i=1}^{n}{\sum_{d|\gcd(i,n)}{\varphi(d)}}
$$
拆开 $\gcd$ 得：
$$
\sum_{i=1}^{n}{\sum_{d|i,d|n}{\varphi(d)}}
$$
改变循环顺序得：
$$
\sum_{d|n}\varphi(d)\sum_{i=1}^{n}[d|i]
$$
化简得：
$$
\sum_{d|n}\varphi(d)\frac{n}{d}
$$
关于推导式子就没了。这时只需将 $\text{phi}$ 预处理，每次询问 $\sqrt{n}$ 复杂度。
- CF1900D Small GCD
先排序，可得以下原公式：
$$
\sum_{i=1}^{n}\sum_{j=1}^{i-1}\gcd(a_i,a_j)(n-i)
$$
带入欧拉反演如下：
$$
\sum_{i=1}^{n}\sum_{j=1}^{i-1}(\sum_{d|\gcd(a_i,a_j)}{\varphi(d)})(n-i)
$$
化简：
$$
\sum_{i=1}^{n}(n-i)\sum_{j=1}^{i-1}\sum_{d|a_i,d|a_j}{\varphi(d)}
$$
$$
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\sum_{j=1}^{i-1}[d|a_j]
$$
$$
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\cdot cnt_{d}
$$
其中我们可以边枚举 $i$ 边处理 $cnt_d$ ，并预处理 $\varphi(x)$ 。因此总时间复杂度为 $O(M+TN\sqrt{M})$ ，$M$ 表示 $a_i$ 的值域，还会有一些小常数，会有点卡常。
果果要求掌握的东西当然是要掌握的咯。
最终形式
$$
\Large{n=\sum_{d|n}^{}}{\varphi(d)}
$$
证明
$$
\large\because n=\sum_{d|n}\sum_{j=1}^{n}{[\gcd(j,n)=d]}
$$
解释一下，首先，这里的 $\gcd(j,n)$ 一定是只有一个值，不可能说有两个不同的值来自同一个 $\gcd(j,n)$ ；其次，为什么这一坨东西等于 $n$ 呢，因为其一说的每个 $\gcd$ 都有唯一确定的值，因此我们只需要枚举 $\gcd$ 的每种可能并枚举所有 $n$ 以内的正整数就必然有且仅有一种可能的 $d$ 满足每组 $\gcd(j,n)=d$ 。
换句话说，因为一个 $\gcd(j,n)$ 只对应唯一一个 $d$ ，这里我们把所有可能的 $\gcd$ 的值和所有的 $j$ 都枚举了自然其值也就等于 $n$ 了（主要就是说明一个不重也不漏）。
$$
\large\therefore \ n=\sum_{d|n}\sum_{j=1}^{\frac{n}{d}}{[\gcd(j,\frac{n}{d})=1]}
$$
这里没什么好说的，目的是把 $\gcd$ 的值化为 $1$ 后能转化成欧拉函数的形式。
$$
\large\therefore n=\sum_{d|n}{\varphi(\frac{n}{d})}
$$
$$
\large\therefore n=\sum_{d|n}{\varphi(d)}
$$
这里是因为每个 $\frac{n}{d}$ 和 $d$ 是对应的，所以能如此转化。
例题
- 多组数据，每组数据给出一个数 $n$ ，求 $\sum_{i=1}^{n}{\gcd(i,n)}$ 。
利用欧拉反演，改变题目公式如下：
$$
\sum_{i=1}^{n}{\sum_{d|\gcd(i,n)}{\varphi(d)}}
$$
拆开 $\gcd$ 得：
$$
\sum_{i=1}^{n}{\sum_{d|i,d|n}{\varphi(d)}}
$$
改变循环顺序得：
$$
\sum_{d|n}\varphi(d)\sum_{i=1}^{n}[d|i]
$$
化简得：
$$
\sum_{d|n}\varphi(d)\frac{n}{d}
$$
关于推导式子就没了。这时只需将 $\text{phi}$ 预处理，每次询问 $\sqrt{n}$ 复杂度。
- CF1900D Small GCD
先排序，可得以下原公式：
$$
\sum_{i=1}^{n}\sum_{j=1}^{i-1}\gcd(a_i,a_j)(n-i)
$$
带入欧拉反演如下：
$$
\sum_{i=1}^{n}\sum_{j=1}^{i-1}(\sum_{d|\gcd(a_i,a_j)}{\varphi(d)})(n-i)
$$
化简：
$$
\sum_{i=1}^{n}(n-i)\sum_{j=1}^{i-1}\sum_{d|a_i,d|a_j}{\varphi(d)}
$$
$$
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\sum_{j=1}^{i-1}[d|a_j]
$$
$$
\sum_{i=1}^{n}(n-i)\sum_{d|a_i}\varphi(d)\cdot cnt_{d}
$$
其中我们可以边枚举 $i$ 边处理 $cnt_d$ ，并预处理 $\varphi(x)$ 。因此总时间复杂度为 $O(M+TN\sqrt{M})$ ，$M$ 表示 $a_i$ 的值域，还会有一些小常数，会有点卡常。