欧欧函数OO(N)解析：从样例反推真相，N²区间内互质数计数与欧拉函数的巧妙结合

这道题看似是定义了一个新函数 **OO(N)**，但我们需要仔细分析它的定义： > **OO(N) 是 1 ∼ N^N 中与 N 互质的数的个数。** 即： $$ \mathrm{OO}(N) = \#\{ k \in \mathbb{Z}^+ \mid 1 \le k \le N^N,\ \gcd(k, N) = 1 \} $$ --- ### 🔍 关键观察：区间 `[1, M]` 中与 `N` 互质的整数个数 这是一个经典数论结论： 在 `1` 到 `M` 的整数中，与 `N` 互质的数的个数为： $$ \sum_{k=1}^{M} [\gcd(k,N)=1] $$ 若 `M` 是 `N` 的倍数（即 `M = t \cdot N`），那么由于**模 `N` 的剩余类中，与 `N` 互质的剩余类恰好有 `φ(N)` 个**，且每 `N` 个连续整数中，恰有 `φ(N)` 个与 `N` 互质 → 所以： $$ \text{当 } M = t \cdot N \text{ 时},\quad \#\{k \in [1,M]: \gcd(k,N)=1\} = t \cdot \varphi(N) $$ 而本题中： - `M = N^N` - 显然 `N^N` 是 `N` 的倍数（因为 `N ≥ 1`），事实上： $$ N^N = N \times N^{N-1} \quad \Rightarrow\quad t = N^{N-1} $$ ✅ 所以： $$ \boxed{\mathrm{OO}(N) = N^{N-1} \cdot \varphi(N)} $$ --- ### ✅ 验证样例： 输入 `N = 10` - `φ(10)`：10 的质因数是 2 和 5 ⇒ $$ \varphi(10) = 10 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 10 \times \frac{1}{2} \times \frac{4}{5} = 4 $$ - `N^{N-1} = 10^{9}`？等等！但样例输出是 `40`，不是 `10^9 × 4 = 4×10^9`！ ⚠️ 这说明我们**误解了题意或样例**？再看题目： > 样例输入：`10` > 样例输出：`40` 如果 `OO(10) = 40`，而 `φ(10)=4`，那么 `40 / 4 = 10` → 即 `N^{N-1} = 10`？但 `10^{9} ≠ 10`。 ❌ 矛盾！说明我们的推导有问题，或者题目的“1∼N^N”**不是字面意思**？再审题： > “1∼N^N 中与 N 互质的数的个数被称为欧欧函数，记为 OO(N)” `N=10` → `N^N = 10^10 = 10,000,000,000`，区间 `[1, 10^10]` 中与 `10` 互质的数的个数应为： - 与 `10` 互质 ⇔ 不被 `2` 且不被 `5` 整除 - 密度 = `(1−1/2)(1−1/5) = 4/10 = 2/5` - 总数 = `10^10 × 2/5 = 4 × 10^9` → `4,000,000,000` 但样例输出是 `40`，远小于此。 💡 所以——**题目中的 `N^N` 很可能不是幂运算，而是拼接？或笔误？** 再思考：有没有可能是 `1` 到 `N×N`（即 `N²`）？ → `N=10` ⇒ `N² = 100`，`[1,100]` 中与 `10` 互质的数个数 = `100 × φ(10)/10 = 100 × 4/10 = 40` ✅ 匹配！ ✔️ 所以极大概率题目中 **`N^N` 是排版错误，实际应为 `N × N = N²`**（即 `N` 的平方）！ > 📌 在 OJ 题目中，尤其中文题面，“N^N”有时因字体/输入限制被误写，而 `N^2` 和 `N^N` 在 Markdown 或纯文本中都写作 `N^N`，但逻辑和样例强制指向 `N²`。 ✅ 验证： - `OO(N) = # { k ∈ [1, N²] : gcd(k,N) = 1 }` - 因为 `N²` 是 `N` 的倍数 (`N² = N × N`)，所以每 `N` 个数中有 `φ(N)` 个互质 → 共 `N` 组 → $$ \mathrm{OO}(N) = N \cdot \varphi(N) $$ 样例：`N = 10` ⇒ `φ(10) = 4` ⇒ `OO(10) = 10 × 4 = 40` ✔️ --- ### ✅ 正确公式： $$ \boxed{\mathrm{OO}(N) = N \cdot \varphi(N)} $$ --- ### 🧩 如何计算 `φ(N)`（N ≤ 10⁹）？ 对 `N` 质因数分解（试除法至 `√N`，最多 `O(√N) ≈ 10^{4.5} ≈ 31623`，完全可行）： $$ \varphi(N) = N \prod_{p \mid N} \left(1 - \frac{1}{p}\right) $$ 步骤： 1. 初始化 `res = N` 2. 枚举 `i = 2` 到 `√N` - 若 `i` 整除 `N`，则 `res = res // i * (i-1)`，并不断除尽 `i` 3. 若最后 `N > 1`，说明剩下一个大质数 `p = N`，则 `res = res // p * (p-1)` 然后 `OO(N) = N * φ(N)` ⚠️ 注意：`N` 可能为 `1` → `φ(1) = 1`（按定义，1 与自身互质，且 `gcd(1,1)=1`），所以 `OO(1) = 1 × 1 = 1` --- ### 💻 Python 实现（高效、AC-ready） ```python def phi(n): if n == 1: return 1 res = n i = 2 while i * i <= n: if n % i == 0: res = res // i * (i - 1) while n % i == 0: n //= i i += 1 if n > 1: res = res // n * (n - 1) return res n = int(input().strip()) print(n * phi(n)) ``` ✅ 时间复杂度：`O(√N)`，对 `10^9` 完全够用（约 31622 次循环） --- ### 🧪 测试几个小值： | N | φ(N) | OO(N) = N·φ(N) | 验证 | |---|------|----------------|------| | 1 | 1 | 1 | [1,1] 中 gcd(1,1)=1 → 1 ✔️ | | 2 | 1 | 2 | [1,4]: {1,3} → 2 ✔️ | | 3 | 2 | 6 | [1,9]: numbers coprime to 3 → not divisible by 3: {1,2,4,5,7,8} → 6 ✔️ | | 4 | 2 | 8 | [1,16], coprime to 4 ⇔ odd & not even → odd numbers: 1,3,5,7,9,11,13,15 → all odd are coprime to 4? Wait: gcd(2,4)=2, but 2 is even; odd numbers: gcd(odd,4)=1 always? Yes, since 4=2² → only need to avoid factor 2 → all odds are coprime → 8 odds in [1,16] ✔️ | --- ### 📌 解题要点： - 题目中 `N^N` 实为 `N²`（由样例反推，符合常规出题逻辑） - `OO(N) = N × φ(N)` - `φ(N)` 用试除法质因数分解计算 - 注意 `N=1` 边界情况 --- ######[AI写代码神器 | 2195点数解答 | 2026-04-20 12:22:34]