欧拉函数（Euler’s totient function），通常用符号φ(n)表示，是数论中的一个重要函数。它表示小于等于n的正整数中，与n互质的数的个数。在ACM竞赛中，欧拉函数经常被用来解决关于整数分解、组合数学等问题。本文将从欧拉函数的基本概念讲起，逐步深入，帮助读者从入门到精通，掌握数学之美。
欧拉函数的定义
欧拉函数φ(n)的定义如下：
φ(n) = {k | 1 ≤ k ≤ n, gcd(k, n) = 1}
其中gcd(k, n)表示k和n的最大公约数。简单来说，φ(n)就是小于等于n的正整数中，与n互质的数的个数。
欧拉函数的性质
φ(n) ≥ 1：由于1与任何数都互质，所以φ(n)至少为1。
φ(n) ≤ n：显然，φ(n)的值不会超过n。
φ(n)是整数：由于gcd(k, n)是整数，所以φ(n)也是整数。
φ(n)是n的因子：由于k与n互质，所以k一定是n的因子。
φ(n)的值只依赖于n的素因子：即如果n可以分解为n = p1^a1 * p2^a2 * … * pk^ak，那么φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * … * (1 - 1/pk)。
欧拉函数的计算方法
计算欧拉函数的方法有很多，以下介绍几种常见的方法：
- 素因子分解法：将n分解为素数的乘积，然后根据欧拉函数的性质计算φ(n)。
def phi(n):
result = n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0:
n //= p
result -= result // p
p += 1
if n > 1:
result -= result // n
return result
- 欧拉筛法：利用筛法找出小于等于n的所有素数，然后根据欧拉函数的性质计算φ(n)。
def sieve_phi(n):
phi = [i for i in range(n + 1)]
for i in range(2, n + 1):
if phi[i] == i: # i是素数
for j in range(i, n + 1, i):
phi[j] -= phi[j] // i
return phi
欧拉函数在ACM竞赛中的应用
求解整数分解问题：利用欧拉函数的性质，可以将整数分解问题转化为求解φ(n)的问题。
求解组合数学问题：欧拉函数在组合数学中有很多应用，例如求解排列组合数、二项式定理等。
求解数论问题：欧拉函数是数论中一个非常重要的工具，可以用来解决很多数论问题。
总结
欧拉函数是数论中的一个重要函数，它在ACM竞赛中有着广泛的应用。通过本文的介绍，相信读者已经对欧拉函数有了基本的了解。在今后的学习中，希望大家能够继续深入探索欧拉函数的魅力，掌握数学之美。