欧拉函数

$$ 欧拉函数\varphi(N)表示，[1, N]中与N互质的数的个数 $$

$$ 如\varphi(6) = 2,只有1， 5与其互质 $$

$$ N的质因数分解结果为p_1^{q_1}p_2^{q_2}p_3^{q_3}\cdots p_m^{q_m} $$

$$ 则\varphi(N) = N(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_m}) $$

$$ 证明：\varphi(N)表示[1, N]中与N互质的数，原来[1, N]中共有N个数 $$

$$ 去除p_1,p_2,p_3\dots p_m的所有倍数，个数变为N - \frac{N}{p_1} - \frac{N}{p_2}-\frac{N}{p_3}-\dots -\frac{N}{p_m} $$

$$ 此时存在数m = p_ip_j被p_i和p_j共删除了两次 $$

$$ 故个数应该+\frac{N}{p_1p_2}+\frac{N}{p_1p_3}+\frac{N}{p_2p_3}+\dots +\frac{N}{p_ip_j} $$

$$ 但是这样又存在数m=p_ip_jp_kp_z被p_ip_j、p_kp_z共加了两次 $$

$$ 因此个数需要-\frac{N}{p_1p_2p_3}-\frac{N}{p_1p_3p_4}-\dots-\frac{N}{p_ip_jp_k} $$

$$ \dots $$

$$ 以此类推，根据容斥原理就能得到 $$

$$ \varphi(N) = N(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_m}) $$

$$ 观察可知\varphi(N)与质因子的次数无关 $$

筛法求欧拉函数

$$ 利用线性筛法 $$

$$ 证明：设[1, N]中的数为a $$

$$ a为质数时\varphi(a)=a-1 $$

$$ a为合数时 $$

$$ 若p_j|a，及p_j是a的最小质因子 $$

$$ 此时:\varphi(ap_j)=a\times p_j(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_k}) $$

$$ \iff p_j\times\varphi(a) $$

$$ 若p_j\nmid a $$

$$ 此时:\varphi(ap_j)=a\times p_j(1-\frac{1}{p_j})(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_k}) $$

$$ \iff (p_j - 1)\varphi(a) $$

欧拉定理

$$ 若a与b互质则有a^{\varphi(b)}\equiv 1(mod b) $$

$$ 如a=5,b=6则有5^{\varphi(6) = 2}\equiv 1(mod 6) $$

$$ 证明：假设[1, b]中所有与b互质的数为a_1,a_2\dots a_{\varphi(b)}(数集1) $$

$$ 因为条件中给出a与b互质，所以aa_1,aa_2\dots aa_{\varphi(b)}(数集2)也与b互质 $$

$$ 上述两个数集在(modb)的含义下是同等的，也即 $$

$$ a^{\varphi(b)}(a_1a_2\dots a_{\varphi(b)}) \equiv (a_1a_2\dots a_{\varphi(b)})(modb) $$

$$ 即a^{\varphi(b)}\equiv1(modb) $$

$$ 当b为质数时，得到费马小定理a^{b-1}\equiv1(modb) $$

AcWing 873. 欧拉函数 原题链接

给定n个正整数aiai，请你求出每个数的欧拉函数。

欧拉函数的定义

1 ~ N 中与 N 互质的数的个数被称为欧拉函数，记为ϕ(N)ϕ(N)。
若在算数基本定理中，N=pa11pa22…pammN=p1a1p2a2…pmam，则：
ϕ(N)ϕ(N) = N∗p1−1p1∗p2−1p2∗…∗pm−1pmN∗p1−1p1∗p2−1p2∗…∗pm−1pm

输入格式

第一行包含整数n。

接下来n行，每行包含一个正整数aiai。

输出格式

输出共n行，每行输出一个正整数aiai的欧拉函数。

数据范围

1≤n≤1001≤n≤100,
1≤ai≤2∗1091≤ai≤2∗109

输入样例：

3
3
6
8

输出样例：

2
2
4

    public static int euler(int x) {
        int res = x;
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                res = res - res / i;
                while (x % i == 0) {
                    x /= i;
                }
            }
        }
        if (x > 1) {
            res = res - res / x;
        }
        return res;
    }

AcWing 874. 筛法求欧拉函数 原题链接

给定一个正整数n，求1~n中每个数的欧拉函数之和。

输入格式

共一行，包含一个整数n。

输出格式

共一行，包含一个整数，表示1~n中每个数的欧拉函数之和。

数据范围

1≤n≤1061≤n≤106

输入样例：

6

输出样例：

12

    static List<Integer> primes = new ArrayList<>();
    static boolean[] st;
    static int[] phi;
    private static void euler(int x) {
        phi[1] = 1;
        for (int i = 2; i <= x; i++) {
            if (!st[i]) {
                primes.add(i);
                phi[i] = i - 1;
            }
            for (int pj = 0; primes.get(pj) <= x / i; pj++) {
                st[primes.get(pj) * i] = true;
                if (i % primes.get(pj) == 0) {
                    phi[primes.get(pj) * i] = phi[i] * primes.get(pj);
                    break;
                }else {
                    phi[primes.get(pj) * i] = phi[i] * (primes.get(pj) - 1);
                }
            }
        }
    }
    public static void main(String[] args) {
        int n = in.nextInt();
        st = new boolean[n + 1];
        phi = new int[n + 1];
        euler(n);
        long res = 0L;
        for (int i = 1; i <= n; i++) {
            res += phi[i];
        }
        out.println(res);
        out.flush();
        out.close();
    }