欧拉函数

欧拉函数求法

暴力求单项的欧拉函数

暴力求单项欧拉函数类似于暴力分解质因数

// 暴力求一项的欧拉函数类似于暴力分解质因数
int single_phi(int n)
{
    int res = 1;
    for (int i = 2; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            res *= (i - 1);
            n /= i;
            while(n % i == 0)
            {
                res *= i;
                n /= i;
            }
        }
    }
    if (n > 1)
    {
        res *= (n - 1);
    }
    return res;
}

求范围内的欧拉函数

求范围内的欧拉函数类似于求欧拉筛

// 把一定范围的欧拉函数求出来类似于欧拉筛
const int maxn = 1e5 + 10;
int res[maxn] = {0};
bool vis[maxn] = {0};
int prime[maxn] = {0};
int cnt = 0;
void phi(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            prime[++cnt] = i;
            res[i] = i - 1; // 如果i是质数，那么phi(i) = i - 1
        }
        for (int j = 1; j <= cnt; j++)
        {
            if (j * prime[i] > n) break;
            vis[i * prime[j]] = 1; // 这里就是把合数筛出去的操作
            if (i % prime[j] == 0) // i和prime[j] 不是互质的
            {
                res[i * prime[j]] = res[i] * prime[j];
                break;
            }
            res[i * prime[j]] = res[i] * (prime[j] - 1); // 这里prime[j] - 1 = res[prime[j]] 这里利用了积性函数的性质 i和prime[j]互质
        }
    }
}