在 CSP - J 备考的强化阶段（第 3 - 4 个月），数学中的欧拉函数是一个重要的知识点。
一、欧拉函数的定义
欧拉函数 φ(n) 表示小于 n 且与 n 互质的数的个数。互质意味着两个数的最大公约数为 1。例如，φ(6) = 2 ，因为小于 6 且与 6 互质的数是 1 和 5 。
二、计算公式（质因数分解）
对于一个正整数 n ，如果其质因数分解式为 n = p₁^a₁ × p₂^a₂ × ··· × pₖ^aₖ ，那么欧拉函数的计算公式为：
φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ··· × (1 - 1/pₖ)
比如，计算 φ(12) ，12 = 2² × 3 ，则 φ(12) = 12 × (1 - 1/2) × (1 - 1/3) = 4 。
三、筛法求欧拉函数
筛法是一种较为高效的方法。
首先，初始化一个数组 phi ，其中 phi[i] 初始值为 i 。
然后，从 2 开始遍历到 n ，如果 phi[i] 等于 i ，说明 i 是质数。对于每个质数 i ，更新所有 i 的倍数 j 的 phi 值，即 phi[j] = phi[j] / i × (i - 1) 。
通过这种方法，可以在较短的时间内求出一定范围内所有数的欧拉函数值。
总之，在备考过程中，要深入理解欧拉函数的定义，熟练掌握其计算公式和筛法。多做相关练习题，加深对知识点的理解和运用，提高解题速度和准确率，为 CSP - J 考试做好充分准备。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
