欧拉函数

Harmony · 2019-01-27 13:49:14 · 个人记录

记录一下欧拉函数的求法。

首先是暴力求法。

求出所有它的质因子，然后用(1 - 1 / pi)减掉。

因为：

phi(x) = x * (1 - 1 / p1) * (1 - 1 / p2) * ... * (1 - 1 / pk)

code:

ll phi(ll x)
{
    ll ans = x;
    for(ll i = 2; i * i <= n; i++)
        if(x % i == 0)
        {
            ans -= ans / i;
            while(x % i == 0)
                x /= i;
        }
    if(x - 1)
        ans -= ans / x;
    return ans;
}

这样复杂度是O(n)的。

然后可以在欧拉筛的时候顺便线性求出来。因为它有三个性质：

1、phi(x) = x - 1, x为质数.
2、phi(i * p1) = phi(i) * p1, p1为质数且p1 | i.
3、phi(i * p1) = phi(i) * (p1 - 1), p1为质数且p1不整除i.

根据欧拉筛里面的筛质数就可以顺便求出phi.

code:

void getphi(int x)
{
    memset(Isprime, true, sizeof(Isprime));
    Isprime[1] = false;
    for(int i = 2; i <= x; i++)
    {
        if(Isprime[i])
            prime[++cnt] = i, phi[i] = i - 1;
        for(int j = 1; j <= cnt && i * prime[j] <= n; j++)
        {
            Isprime[i * prime[j]] = false;
            if(i % prime[j])
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            else
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}