欧拉函数：数学中的神奇公式

欧拉函数是数论中的一个重要函数，它在密码学、计算机科学等领域中有广泛的应用。下面，我们将深入探讨欧拉函数的定义、性质和应用。

什么是欧拉函数？

欧拉函数，又称欧拉-费马函数，是指小于等于正整数n的数中与n互质的数的个数，记为φ(n)。例如，φ(6)=2，因为小于等于6且与6互质的数只有1和5两个。

欧拉函数的计算方法

欧拉函数的计算方法有多种，其中一种常见的方法是欧拉筛法。欧拉筛法的基本思想是从小到大枚举每个数，对于每个数，如果它是质数，则将它的倍数标记为合数，同时计算出它的欧拉函数值。

int phi[N], prime[N], cnt;
bool st[N];

void euler_sieve(int n) {
    phi[1] = 1;
    for (int i = 2; i