上一篇介绍了欧拉函数的推导，这里在此基础上，利用欧拉函数求解一个实际的问题，说是利用欧拉函数，但其实因为想法太原始，思维太简单，大量的工作都是重新推导，有利用欧拉函数的地方，但也不算多。

####问题说明####

问题的描述比较简单，给定一个数 N，求解 ∑ gcd (i, N) (1 <= i <= N)。

####分解#### 和前面欧拉函数的推导类似，假设数 N 可以分解为两个数 p 和 q 的乘积 （且 p 和 q 互素，p 和 q 都不为 1）。

####具体思路#### 首先假设对于一个数 N，令 F(N) = ∑ gcd (i, N) (1 <= i <= N)。还是和前面欧拉函数的推导类似，我们希望能通过 F(p) 和 F(q) 推导出 F(N)。这样就可以将原始问题化解为更小的问题。通过递归或者分治的方法去求解。

对于数 p 而言，将[1, p] 中的与 p 不互素的每一个数与 p 的最大公因子进行累加，得到的值应该为 F(p) - φ(p) 其中 φ(p) 为欧拉函数，用公式表示即为 ∑ gcd (i, p) = F(p) - φ(p) (1 <= i <= p && gcd (p, i) != 1)。这点应该不难理解，因为根据定义 F(p) 为 ∑ gcd (i, p) (1 <= i <= p)。而所有与 p 互素的数一共有 φ(p) 个，它们与 p 的最大公因子都为 1，因此用 F(p) 直接减去 φ(p)，即为[1, p] 中与 p 不互素的每一个数与 p 的最大公因子累加之和。

同理对于数 q 而言，[1, q] 中与 q 不互素的每一个数与 q 的最大公因子累加之和为 F(q) - φ(q) 。

现在我们就是希望推导出 [1, N] 中与 N 不互素的每个数与 N 的最大公因子累加之和，得到这个和之后再加上 φ(N)，则即为所求。

####分步推导####

这里将推导分为三步，

第一步是推导 [1, N] 中与 N 不互素且最大公因子只为 p 的因子的数与 N 的最大公因子累加之和，表述有点拗口，用公式表示就是 ∑ gcd (i, N) (1 <= i <= N && (i, N) != 1 && gcd(i, N) == gcd(i, p))

对于上面所说的累加之和为 (F(p) - φ(p)) * φ(q)，为什么这么说，首先根据前面的介绍 F(p) - φ(p) 为 [1, p] 中与 p 不互素的每个数与 p 的最大公因子累加之和。用 [1, p]中每个不与 p 互素的数乘以 [1, q] 中所有与 q 互素的数与 N 的最大公因子都只是 q 的因子，即为我们上面第一步所要求的那些数。而所有这些数的累加之和即为 (F(p) - φ(p)) * φ(q) 。

第二步推导 [1, N] 中与 N 不互素且最大公因子只为 q 的因子的数与 N 的最大公因子累加之和。用公式表示就是 ∑ gcd (i, N) (1 <= i <= N && (i, N) != 1 && gcd(i, N) == gcd(i, q))。根据第一步的推导结果，我们知道 (F(q) - φ(q)) * φ(p) 即为所求。

第三步我们要推导 [1, N] 中与 N 不互素且既含有 p 的因子又含有 q 的因子的数与 N 的最大公因子累加之和。对于 [1, p] 中每一个不与 p 互素的数，乘上[1, q] 中任意一个不与 q 互素的数 t, 所得到的数都是一个既含有 p 的因且又含有 q 的因子的数。且这些数与 N 的最大公因子累加之和为 (F(p) - φ(p)) * gcd (t, q)。这个理解应该不难，因为对于 [1, p] 中的每一个不与 p 互素的数乘上 [1, q]中任意一个不与 q 互素的数 t，所得到的数与 N 都会有一个因子 gcd (t, q)。将这个最大公因子提取出来，剩下的即为 F(p) - φ(p) 了。

对于[1, p] 中每一个不与 p 互素的数与 [1, q] 中每一个不与 q 互素的数相乘所得到的数与 N 都有公因子是 p 的因子也有公因子是 q 的因子。而这些数与 N 的最大公因子累加之和即为 (F(p) - φ(p)) * ∑ gcd (t, q) (1 <= t <= q && gcd (t, q) != 1)。即为 (F(p) - φ(p)) * (F(q) - φ(q)) 。

####求解####

有了前面三步的推导，再加上 φ(N) 即为所求，而根据前面欧拉函数的推导 φ(N) = φ(p) * φ(q)。

所以 F(N) = (F(p) - φ(p)) * (F(q) - φ(q)) + (F(p) - φ(p)) * φ(q) + (F(q) - φ(q)) * φ(p) + φ(p) * φ(q) 。 进行变换得到 F(N) = (F(p) - φ(p) + φ(p)) * (F(q) - φ(q) + φ(q)) 。即 F(N) = F(p) * F(q)。

有了前面的推导公式，通过因式分解，能将 N 分解为 N = p1^e1 * p2^e2 * … * pn^en 的形式。那么 F(N) = F(p1^e1) * F(p2^e2) * … * F(pn^en) 。

而对于 F(p^e) 的值我们比较容易求解。令 M = p^e 。对与 [1, M] 中的数与 M 有最大公因子为 p^e 的数有 1 个， 与 M 有最大公因子 p^(e-1) 的数有 (p - 1) ，这个比较好理解，用 p^(e-1) 乘上[1, p]中任何一个不是 p 的倍数的数都满足条件，同理与 M 有最大公因子 p^(e-2) 的数有 (p^2 - p)个。这里也可以理解为用 p^(e-2)乘上[1, p^2] 中一个不是 p 的倍数的数即可，因为乘上是 p 的倍数的数，其与 M 的最大公因子都比 p^(e-2) 要大。同理所有与 M 有公因子 p^(e-k) 的数的个数为 p^k - p^(k-1) 。因为用 p^(e-k) 乘上 [1, p^k] 中任何一个不是 p 的倍数的数都与 M 有最大公因子 p^(e-k)。

所以 F(M) = p^e * 1 + ∑ {(p^(e-k)) * (p^k - p^(k-1))} (1 <= k <= e) 进行变换得到 F(M) = p^e + e * (p^e - p^(e-1)) 。