当前位置：首页 > news >正文

欧拉函数

news 来源：原创 2024/5/4 5:04:15

欧拉函数

欧拉函数就是求小于 $n$ 且与 $n$ 互质的整数个数

设 $n$ 的唯一分解式为 $n=p_1^{a_1}p_2^{a_2}...p_n^{a_n}$

$φ(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_n})$

求欧拉函数

求单个数的欧拉函数

ll euler_phi(ll n) {
    int m = sqrt(n + 0.5);
    ll ans = n;
    for (int i = 2; i <= m; 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;
}

埃氏筛法求欧拉函数

根据上述公式，类似埃氏筛，每求得一个素数就更新其倍数所有的 $p h i$ 值

int phi[maxn];

void phi_table(int n) {
    memset(phi, 0, sizeof phi);
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
        if (!phi[i]) {
            for (int j = i; j <= n; j += i) {
                if (!phi[j]) phi[j] = j;
                phi[j] = phi[j] / i * (i - 1);
            }
        }
}

欧拉筛法求欧拉函数

使用此方法需要知道欧拉函数的以下性质：

对于素数 $p$ ，若 $n\%i==0$ ，那么 $\varphi(pn)= p*\varphi(n)$ ；若 $n\%i!=0$ ，那么 $\varphi(pn)= \varphi(p)\varphi(n) = (p-1)*\varphi(n)$
若 $n$ 为某一素数的幂次，那么 $\varphi(p^a)=(p-1)*p^{a-1}$

证明：
在这里插入图片描述

vector<int> prime;
bitset<maxn> vis;
int phi[maxn];

void euler() {
    phi[1] = 1;
    for (int i = 2; i < maxn; i++) {
        if (!vis[i]) {
            phi[i] = i - 1;
            prime.push_back(i);
        }
        for (int j = 0; j < prime.size() && i * prime[j] < maxn; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j]) {
                prime[i * prime[j]] = phi[i] * (prime[j] - 1);
            } else {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}

性质

当 $m, n$ 互质时，有 $\varphi(m*n)= \varphi(m)*\varphi(n)$
对于素数 $p$ ，若 $n\%i==0$ ，那么 $\varphi(pn)= p*\varphi(n)$ ；若 $n\%i!=0$ ，那么 $\varphi(pn)= \varphi(p)\varphi(n) = (p-1)*\varphi(n)$
对于互质的 $x$ 与 $p$ ，有 $x^{\varphi(p)}≡1(mod~p)$ ，因此 $x$ 的逆元为 $x^{\varphi(p)}-1$ ，即欧拉定理。特别地，当 $p$ 为质数时， $\varphi(p)=p-1$ ，此时逆元为 $x^{p-2}$ ，即费马小定理 $x^{p-1} \equiv 1(mod~~p)$
当 $n$ 为奇数时， $\varphi(2*n)=\varphi(n)$

证明：因为 $n$ 为奇数，那么 $2 n$ 为偶数，偶数和偶数一定不互素，所以只需考虑 $2 n$ 和小于它的奇数互素的情况
$n > 1$ ，不大于 $n$ 且和 $n$ 互质的所有正整数的和是 $\frac{\varphi(n)*n}{2}$