06-数学相关/03-欧拉函数

欧拉函数 [math]\displaystyle{ \varphi(n) }[/math] 表示 [math]\displaystyle{ 1\sim n }[/math] 中与 [math]\displaystyle{ n }[/math] 互质的数的个数。

求单个欧拉函数

[math]\displaystyle{ O(\sqrt{n}) }[/math]

[math]\displaystyle{ \varphi(n)=n\times \prod_{p\mid n}\left(1-\frac{1}{p}\right) }[/math]

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

线性筛求欧拉函数

[math]\displaystyle{ O(n) }[/math]，同时求出 [math]\displaystyle{ 1\sim n }[/math] 所有数的欧拉函数值。

const int MAXN = 40000;
bool p[MAXN + 5];
int phi[MAXN + 5];
vector<int> pri;

void get_phi(int n)
{
    for (int i = 1; i <= n; i++)
        p[i] = true;
    p[0] = p[1] = false;
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (p[i])
        {
            pri.push_back(i);
            phi[i] = i - 1;
        }
        for (int j = 0; j < pri.size(); j++)
        {
            if (1LL * i * pri[j] > n)
                break;
            p[i * pri[j]] = false;
            if (i % pri[j] == 0)
            {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            else
                phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }
}

欧拉函数性质

- 若 [math]\displaystyle{ p }[/math] 是质数，[math]\displaystyle{ \varphi(p)=p-1 }[/math] - 若 [math]\displaystyle{ p }[/math] 是质数，[math]\displaystyle{ \varphi(p^k)=p^k-p^{k-1} }[/math] - 若 [math]\displaystyle{ \gcd(a,b)=1 }[/math]，则 [math]\displaystyle{ \varphi(ab)=\varphi(a)\times\varphi(b) }[/math]（积性函数） - [math]\displaystyle{ \sum_{d\mid n}\varphi(d)=n }[/math]

欧拉定理

若 [math]\displaystyle{ \gcd(a,m)=1 }[/math]，则：

[math]\displaystyle{ a^{\varphi(m)}\equiv 1\pmod m }[/math]

当 [math]\displaystyle{ m }[/math] 为质数时就是费马小定理。