Python实现欧欧函数计算，解决数论难题

### 💡思路分析 本题要求计算欧欧函数 \(OO(N)\)，即 \(1\sim N^N\) 中与 \(N\) 互质的数的个数。可以利用欧拉函数的性质来解决。欧拉函数 \(\varphi(n)\) 表示小于等于 \(n\) 的正整数中与 \(n\) 互质的数的个数。 对于一个数 \(N\)，如果 \(N = p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{k}^{a_{k}}\) 是 \(N\) 的质因数分解形式，那么欧拉函数 \(\varphi(N)=N\prod_{i = 1}^{k}(1-\frac{1}{p_{i}})\)。 而 \(1\sim N^N\) 中与 \(N\) 互质的数的个数可以通过欧拉函数的性质得到，即 \(OO(N)=N^{N - 1}\varphi(N)\)。 ### 📝代码实现 ```python def euler_phi(n): # 初始化结果为 n result = n # 从 2 开始遍历到 sqrt(n) p = 2 while p * p <= n: if n % p == 0: # 找到一个质因数 p while n % p == 0: n //= p # 根据欧拉函数公式更新结果 result = result // p * (p - 1) p += 1 # 如果 n 大于 1，说明 n 本身是一个质数 if n > 1: result = result // n * (n - 1) return result # 读取输入的 N N = int(input()) # 计算 OO(N) oo_n = (N ** (N - 1)) * euler_phi(N) # 输出结果 print(oo_n) ``` ### 代码解释 1. **`euler_phi` 函数**：该函数用于计算欧拉函数 \(\varphi(N)\)。通过遍历从 \(2\) 到 \(\sqrt{N}\) 的所有数，找到 \(N\) 的质因数，并根据欧拉函数公式更新结果。 2. **主程序**：读取输入的 \(N\)，调用 `euler_phi` 函数计算 \(\varphi(N)\)，然后根据 \(OO(N)=N^{N - 1}\varphi(N)\) 计算 \(OO(N)\) 并输出结果。 ### 复杂度分析 - **时间复杂度**：计算欧拉函数的时间复杂度为 \(O(\sqrt{N})\)，计算 \(N^{N - 1}\) 的时间复杂度为 \(O(N\log N)\)，因此总的时间复杂度为 \(O(N\log N+\sqrt{N})\)。 - **空间复杂度**：代码只使用了常数级的额外空间，因此空间复杂度为 \(O(1)\)。 ######[AI问答 | 681点数解答 | 2026-04-20 12:19:22]