3、歐拉函數

1、定義：

1~n 中與 n 互質的數的個數

例如：6 的有 1 2 3 4 5 6 其中，與 n 互質 的 數的個數為 2個分別是：1、5

2、計算：

$ N = p_1^{a1} × p_2^{a2} × p_3^{a3} × … × p_k^{ak} $（例如：6 = 2¹ × 3¹）

$ \phi(N) = N(1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) …(1 - \frac{1}{p_k}) $

import java.util.*;public class Main {static int[] vs = new int[10010];public static void main(String[] args) {Scanner sc = new Scanner(System.in);int t = 1;while(t-- > 0) {int n = 6;int ans = n;for(int i = 2;i <= n / i;i++) {if(n % i == 0) {ans = ans / i * (i - 1);while(n % i == 0) n /= i;}}if(n > 1) ans = ans / n * (n-1);System.out.println(ans);}sc.close();}
}

import java.util.*;
public class Main{static int N = 1000010;static int index = 0;static int[] p = new int[N];static boolean[] st = new boolean[N];static int[] phi = new int[N];public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();phi[1] = 1;for(int i = 2;i <= n;i++) {if(!st[i]) {phi[i] = i - 1;p[index++] = i;}for(int j = 0;p[j] <= n / i;j++) {st[p[j] * i] = true;if(i % p[j] == 0) {phi[p[j] * i] = phi[i] * p[j];break;}phi[p[j] * i] = phi[i] * (p[j] - 1);}}long ans = 0;for(int i = 1;i <= n;i++) {ans += phi[i];}System.out.println(ans);sc.close();}
}

3、拓展

對于 1~m 中，與 n 互質的數的個數的 特殊情況

• 如果 n 為質數：直接計算，結果為：$ m - [\frac{m}{n}]（表示向向下取整，即為：(int)(m/n)） $
• 如果 m 是 n 的倍數，即：$ m=k \cdot n $，結果為：$ k \cdot \phi(n) （其中\phi(n)是n的歐拉數） $
• 如果 m 是 n 的次方倍，即：$ m = n^k $，結果為：$ m=n^{k-1} \cdot n ==> 結果為：n^{k-1} \phi(n) $

用處：如果 a 與 b 互質，那末有：$ \bbox[5px,border:2px solid greenyellow]
{
a^{\phi(b)} \equiv 1 \pmod{b} ===> a^{\phi(b)} - mod - b = 1
}
$

4、快速冪

1、原理

對于一個數 $ a^k $必定可以拆成$ a^{x_1} * a^{x_2} * … * a^{x_k} $,因為：k必定能轉化為二進制，而二進制的有1的一項，即為x_k，因此，可以計算每一項的$ a^x $進行計算。

因此要預處理計算出：$ a^{20}、a^{21}、a^{22}…a^{2k} $,之后，將$ a^k $分解，計算。

import java.util.*;
public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);long n = 1;while(n-- > 0) {long a = 27; // 底數long k = 36; // 指數long p = (long) (1e9 + 7); // 取模System.out.println(qmi(a,k,p));}sc.close();}static long qmi(long a,long k,long p){long res = 1; // 初始值為 1while(k != 0) {// 如果 k（指數）的末尾為 1，那末直接計算// res = a^x_1 * .. * a^x_kif((k & 1) == 1) res = res * a % p;k >>= 1; // 指數向右移動一位a = a * a % p; // 持續計算預處理}return res; // 返回的就是 a^k % p 的結果}
}

2、費馬定理

$ b^{p-1} \equiv 1 \pmod{p} $ 條件：p 與 b 必須互質，也可也是，p 是質數

因此：由此可知，求 b 的模 p 的逆元，即為：$ b^{p-2} $即為 b 模 p 的逆元

public class Main {public static void main(String[] args) {// 求 n！ 模 1e9 + 7 的逆元int n = 3;int mod = 1000000007;long ans = 1;for(int i = 1;i <= n;i++)ans = ans * qmi(i,mod - 2,mod) % mod;System.out.println(ans);}static long qmi(long a,long k,long p){long res = 1;while(k != 0) {if((k & 1) == 1)res = res * a % p;k >>= 1;a = a * a % p;}return res;}
}

5、組合數

1、快速計算 $ C_n^m $的值

1、條件：n <= 20000

2、原理：$ C_n^m = C_{n-1}^m + C_{n-1}^{m-1} $ 類似于動態規劃

public class Main {static int[][] c = new int[20010][20010];public static void main(String[] args) {long s = System.currentTimeMillis();int n = 20000;for(int i = 0;i < n;i++) {for(int j = 0;j <= i;j++) {if(j == 0) c[i][j] = 1;else c[i][j] = c[i-1][j] + c[i-1][j-1];}}System.out.println(c[6][2]);System.out.println(System.currentTimeMillis() - s);}
}

6、容斥原理

主要用于計算集合并集的個數，除去相交的個數。

容斥原理：$ S_1 ∪ S_2 ∪ S_3 = S_1 ∩ S_2 ∩ S_3 - (S_1 ∩ S_2) - (S_1 ∩ S_3) - (S_2 ∩ S_3) + (S_1 ∩ S_2 ∩ S_3) $

要求從 1~ n 中任意選擇任意個數，那末可以用位運算來遍歷這些所有的選擇。