算法基础04

• 数论
  • 质数
  • 约数
• 欧拉函数
• 快速幂
• 扩展欧几里得
• 高斯消元
• 组合计数
• 容斥原理
• 简单博弈论

a/b上取整 = (a + b - 1) / b

数论

质数

在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数

（1）质数的判定——试除法

O(sqrt(n))

写成i <= n / i i * i < n可能会溢出

static boolean is_prime(int n){
    if(n < 2)return false;
    for(int i = 2; i <= n / i; i++){
        if(n % i == 0)return false;
    }
    return true;
}

（2）分解质因数——试除法

O(logn) ~ O(sqrt(n))

从小到大枚举所有数

n中最多只包含一个大于sqrt(n)的质因子

static void divide(int n){
	for(int i = 2; i <= n / i; i++){
		if(n % i == 0){//成立则i一定为质数
            int s = 0;//幂
            while(n%i == 0){
                n /= i;
                s++;
            }
            System.out.println(i + " " + s);
        }
	}
    if(n > 1)println(n + " 1");
}

（3）质数筛

A. 埃式筛法：复杂度O(nloglogn)

质数定理：1~n中有n/lnn个质数

static int N = 100010;
static boolean[] st = new boolean[N];
static int[] primes = new int[N];
static int cnt;

void get_prime(int n){
    for(int i = 2; i <= n; i++){
        if(!st[i])
            primes[cnt++] = i;
            for(int j = i + i; j <= n; j += i)st[j] = true;//化简为只筛质数的倍数
    }
}

B. 线性筛法：复杂度O(n)

合数n只会被其最小质因子筛掉

1. i % pj == 0
  pj一定是i的最小质因子,pj一定是pj*i的最小质因子
2. i% pj != 0
  pj一定小于i的所有质因子,pj也一定是pj*i的最小质因子

static int N = 100010;
static boolean[] st = new boolean[N];
static int[] primes = new int[N];
static int cnt;

void get_prime(int n){
    for(int i = 2; i <= n; i++){
        if(!st[i])primes[cnt++] = i;
        for(int j = 0; primes[j] <= n / i; j++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0)break;
        }
    }
}

1. primes[j] <= n / i
保证primes[j] * i <= n st不会超出范围
2. 筛数有顺序,有规范 -> 合数pj*i只会被其最小质因数筛掉

//1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j]<i的
//最小质因子,所以primes[j]*i的最小质因子就是primes[j];
//2)当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是
//prime[j]，之后接着用st[primes[j+1]*i]=true去筛合数时，就不是用最小质因子去更新了,因为i有最小
//质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子，此时就应该
//退出循环，避免之后重复进行筛选。

约数

（1）试除法求一个数的所有约数

复杂度O(sqrt(n))

static void get_divisors(int x) {
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 1; i <= x / i; i++) {
        if (x % i == 0) {
            list.add(i);
            if (i != x / i) list.add(x / i);
        }
    }
    Collections.sort(list);//排序复杂度logn*loglogn
    for(int i : list){
        System.out.print(i + " ");
    }
    System.out.println();
}

所有int范围内的质数个数：105097565

所有int范围内的整数(2147483647)，约数个数最多的数是1600个(2095133040)（一个数n的约数个数可以用log(n)估计）

1百万以内：最大一个720720 ->有240个约数

（2）约数个数

基于算数基本定理：

$$N = P_1^{\alpha_1}P_2^{\alpha_2}P_3^{\alpha_3}...P_k^{\alpha_k}$$ $$d = P_1^{\beta_1}P_2^{\beta_2}P_3^{\beta_3}...P_k^{\beta_k} (0<=\beta_i<=\alpha_i)$$

约数个数：

$$(\alpha_1 + 1)(\alpha_2 + 1)(\alpha_3 + 1)...(\alpha_k + 1)$$

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class getDivisors_number {
    static int mod = (int) (1e9 + 7);
    public static void main(String[] args){
        Map<Integer, Integer> map = new HashMap<>();//创建一个哈希表
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        while(n-- != 0){
            int x = sc.nextInt();
            for(int i = 2; i <= x / i; i++){
                while(x % i == 0){
                    x /= i;
                    map.put(i, map.getOrDefault(i, 0) + 1);
                }
            }
            if(x > 1)map.put(x, map.getOrDefault(x, 0) + 1);
        }

        long res1 = 1L;//res1 -> 约数个数
        for(Integer key : map.keySet())res1 = res1 * (map.get(key) + 1) % mod;
        System.out.println(res1);
    }
}

（3）约数之和

约数之和：

$$(P_1^0+P_1^1+...+P_1^{\alpha_1})*(P_2^0+P_2^1+...+P_2^{\alpha_2})*...*(P_k^0+P_k^1+...+P_k^{\alpha_k})$$

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class getDivisors_Sum {
    static int mod = (int) (1e9 + 7);
    public static void main(String[] args){
        Map<Integer, Integer> map = new HashMap<>();//创建一个哈希表
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        while(n-- != 0){
            int x = sc.nextInt();
            for(int i = 2; i <= x / i; i++){
                while(x % i == 0){
                    x /= i;
                    map.put(i, map.getOrDefault(i, 0) + 1);
                }
            }
            if(x > 1)map.put(x, map.getOrDefault(x, 0) + 1);
        }

        long res2 = 1L;
        for(Integer p : map.keySet()){
            int a = map.get(p);
            long t = 1L;
            while(a -- != 0)t = (t * p + 1) % mod;
            res2 = res2 * t % mod;
        }
        System.out.println(res2);
    }
}

（4）最大公因数

辗转相除法O(logn)：

import java.util.Scanner;

public class gcd {
    static int GCD(int a, int b){
        return b == 0 ? a : GCD(b, a % b);
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while(n-- != 0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            System.out.println(GCD(a, b));
        }
    }
}

欧拉函数

$$\varphi(n) = 1到n中与n互质的数的个数$$

特别的，1和任何n互质，n和n不互质

（互质：两个数的公因数只有1）

分解质因数

$$N = P_1^{\alpha_1}P_2^{\alpha_2}P_3^{\alpha_3}...P_k^{\alpha_k}$$ $$\varphi(n)=N(1-\frac{1}{P_1})(1-\frac{1}{P_2})...(1-\frac{1}{P_k})$$

证明：

容斥原理：

1. 从1~N中去掉p1,p2,…,pk的所有倍数

$$N-\frac{N}{P_1}-\frac{N}{P_2}-...--\frac{N}{P_k}$$

1. 加上所有pi*pj的倍数

$$+\frac{N}{P_1P_2}+\frac{N}{P_1P_3}+...$$

1. 减去所有pi pj pk的倍数

$$-\frac{N}{P_1P_2P_3}-\frac{N}{P_1P_2P_4}-...$$

1. ….

代码：

复杂度O(sqrt(n))

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

筛法求欧拉函数（在线性筛法的基础上）

复杂度：O(n)

static int N = 1000010;
static int[] primes = new int[N];
static int[] phi = new int[N];
static boolean[] st = new boolean[N];
static int cnt;

static long get_Euler(int n) {
    long res = 1;
    
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            primes[cnt++] = i;
            phi[i] = i - 1;//针对质数的欧拉函数
        }
        for (int j = 0; primes[j] <= n / i; j++) {
            st[i * primes[j]] = true;
            
            if (i % primes[j] == 0) {//pj是i的最小质因数
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
           phi[i * primes[j]] = phi[i] * (primes[j] - 1);//pj小于i的最小质因数
        }
    }

    for(int i = 1; i <= n; i++){
        res += phi[i];
    }
    return res;
}

补充：

• 欧拉定理：

若a与n互质，则有

$$a^{\varphi(n)} mod n = 1$$

• 费马小定理：

当p为质数，整数a不是p的倍数（互质的更弱条件）时:

$$a^{p-1} mod p = 1$$

快速幂

快速求出a^k mod p的结果

复杂度：O(log k)

static int PMI(int a, int b, int p){//a ^ b % p
    int res = 1 % p;
    while(b != 0) {
        if ((b & 1) == 1) res = (int)((long)res * a % p);
        b >>= 1;
        a = (int) ((long)a * a % p);
    }
    return res;
}

扩展欧几里得算法

裴蜀定理：对于任意正整数a,b，那么一定存在非零整数x,y，使得：ax + by = gcd(a,b)

裴蜀定理      -------   扩展欧几里得算法
可以求出最大公约数d，且可以求出 ax + by = d 的系数 
(a, b)
ax + by = d
a' = a / d
b' = b / d

//任意一组解
x = x0 + kb'
y = y0 + ka'

证明过程：
由
ax0 + by0 = d
ax' + by' = d

推出:
a(x' - x0) = b(y0 - y')
a'(x' - x0) = b'(y0 - y')

=> b'|a'(x' - x0)
由于a' 与 b' 互质
=> b'|(x' - x0)


=> x' - x0 = kb'

最小正整数解：

x = x0 % (b / d)

y = y0 % (a / d)

同时有以下小性质：

gcd(a,b) = 1，即a与b互质时：它们最大不能凑出来的数是`(a - 1) (b - 1) + 1`*

bx′+(a%b)y′=gcd(b,a%b)

bx′+(a−⌊a/b⌋∗b)y′=gcd(b,a%b)

有ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)=gcd(a,b)

故x=y′,y=x′−⌊a/b⌋∗y′

算法复杂度：log(n)

import java.util.Scanner;

public class exgcd {
    static int[] x = new int[1];
    static int[] y = new int[1];

    public static void exGCD(int a, int b, int[] x, int[] y) {
        if (b == 0) {//递归出口(找到了最大公约数)
            x[0] = 1;
            y[0] = 0;
            return;
        }
        exGCD(b, a % b, y, x);
        y[0] -= (a / b) * x[0];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n-- != 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            exGCD(a, b, x, y);
            System.out.println(x[0] + " " + y[0]);
        }
    }
}

解线性同余方程

对于求解更一般的方程 ax+by=c，设 d=gcd(a,b) 则其有解当且仅当 d|c

求解方法如下：

a(x0∗c/d)+b(y0∗c/d)=c

故有特解：x′=x0∗c/d，y′=y0∗c/d

import java.io.*;

public class Main{
    static int[] x = new int[1];
    static int[] y = new int[1];
    
    public static int exGCD(int a, int b, int[] x, int[] y) {
        if (b == 0) {//递归出口(找到了最大公约数)
            x[0] = 1;
            y[0] = 0;
            return a;
        }
        int d = exGCD(b, a % b, y, x);
        y[0] -= (a / b) * x[0];
        return d;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        while(n -- != 0){
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int m = Integer.parseInt(s[2]);
            int d = exGCD(a, m, x, y);
            if(b % d == 0)System.out.println((long)x[0] * b / d % m);
            else System.out.println("impossible");
        }
    }
}

中国剩余定理

先略过了CPU跟它不兼容

高斯消元解线性方程

用线代矩阵形式求解n元方程组，时间复杂度：O(n^3)

• 列满秩：唯一解

• 存在0x = 非零 : 无解

• 存在0x = 0：无穷多解

算法实现：

• 化为n*(n+1)的矩阵
• 枚举每一列（1到n列）
  • 找到绝对值最大的一行
  • 将该行换到最上面
  • 将该行第一个数变成1
  • 将下面所有行的第c列消成零
• （得到上三角矩阵）
• 回溯消去上面对应列的系数

代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 110;
    static int n;
    static double[][] a = new double[N][N];

    static double eps = 1e-6;

    static int Gauss() {
        int c, r;
        for (c = 0, r = 0; c < n; c++) {//枚举每一列c(n列)
            int t = r;
            for (int i = r; i < n; i++)
                if (Math.abs(a[i][c]) > Math.abs(a[t][c])) t = i;

            //为零就跳过
            if (Math.abs(a[t][c]) < eps) continue;

            //交换
            double[] temp = a[t];
            a[t] = a[r];
            a[r] = temp;

            for (int i = n; i >= c; i--)//逆序操作,避免a[r][c]先被操作
                //如果a[r][c]已经是1了就跳过
                if (Math.abs(a[r][c] - 1) > eps) a[r][i] /= a[r][c];

            //将r下面的每一行的第c列化为0
            for (int i = r + 1; i < n; i++)
                if (Math.abs(a[i][c]) > eps)
                    for (int j = n; j >= c; j--)
                        a[i][j] -= a[r][j] * a[i][c];
            r++;
        }

        if (r < n) {
            for (int i = r; i < n; i++) {
                if (Math.abs(a[i][n]) > eps) return 2;//无解 0 = !0
            }
            return 1;//有无穷多组解 0 = 0
        }

        //回溯消去上面对应列的系数
        for (int i = n - 1; i >= 0; i--) {//倒序求真解
            for (int j = i + 1; j < n; j++)
                a[i][n] -= a[j][n] * a[i][j];//神来之笔 大道至简
        }
        return 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            for (int j = 0; j < n + 1; j++) {
                a[i][j] = Double.parseDouble(s[j]);
            }
        }
        int t = Gauss();
        if (t == 2) System.out.println("No solution");
        else if (t == 1) System.out.println("Infinite group solutions");
        else {
            for (int i = 0; i < n; i++) {
                if (Math.abs(a[i][n]) < eps) a[i][n] = 0;//去掉输出-0.00的情况
                System.out.printf("%.2f\n", a[i][n]);
            }
        }
    }
}

组合数

核心公式：

$$C_a^b=C_{a-1}^b+C_{a-1}^{b-1}$$

1. 范围：10万组询问 1<= b<=a<=2000： O(n^2)

   递推：

   import java.io.*;
   
   public class combination01 {
       static int N = 2010;//2000
   
       static int[][] c = new int[N][N];
   
       static int mod = (int) 1e9 + 7;
   
       static void init() {
           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]) % mod;
               }
       }

2. 范围：1万组询问 1<= b<=a<=10^5： O(nlogn)

   预处理：

   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   
   public class Main {
       static int N = 100010;
       static int[] fact = new int[N];//阶乘
       static int[] infact = new int[N];//阶乘逆元
   
       static int mod = (int) 1e9 + 7;
   
       static int qmi(int a, int b, int p) {
           int res = 1 % p;
           while (b != 0) {
               if ((b & 1) == 1) res = (int) ((long) res * a % mod);
               a = (int) ((long) a * a % p);
               b >>= 1;
           }
           return res;
       }
   
       public static void main(String[] args) throws IOException {
           //预处理
           fact[0] = infact[0] = 1;
           for (int i = 1; i < N; i++) {
               fact[i] = (int) ((long) fact[i - 1] * i % mod);
               infact[i] = (int) ((long) infact[i - 1] * qmi(i, mod - 2, mod) % mod);//逆元
           }
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           int n = Integer.parseInt(br.readLine());
           while (n-- != 0) {
               String[] s = br.readLine().split(" ");
               int a = Integer.parseInt(s[0]);
               int b = Integer.parseInt(s[1]);
               System.out.println(((long)fact[a] * infact[b]) % mod * infact[a - b] % mod);
           }
       }
   }

   或者倒序求出阶乘逆元：复杂度降低为O(n)

   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   
   public class Main {
       static int N = 100010;
       static int[] fact = new int[N];//阶乘
       static int[] infact = new int[N];//阶乘逆元
   
       static int mod = (int) 1e9 + 7;
   
       static int qmi(int a, int b, int p) {
           int res = 1 % p;
           while (b != 0) {
               if ((b & 1) == 1) res = (int) ((long) res * a % mod);
               a = (int) ((long) a * a % p);
               b >>= 1;
           }
           return res;
       }
   
       public static void main(String[] args) throws IOException {
           //预处理
           fact[0] = infact[0] = 1;
           for (int i = 1; i < N; i++) {
               fact[i] = (int) ((long) fact[i - 1] * i % mod);
           }
           // System.out.println(fact[N-1]);
           infact[N - 1] = qmi(fact[N - 1], mod - 2, mod); 
           // System.out.println(infact[N-1]);
           for(int i = N - 2; i >= 1; i--){
               infact[i] = (int)((long)infact[i+1] * (i + 1) % mod);
           }
           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           int n = Integer.parseInt(br.readLine());
           while (n-- != 0) {
               String[] s = br.readLine().split(" ");
               int a = Integer.parseInt(s[0]);
               int b = Integer.parseInt(s[1]);
               System.out.println(((long)fact[a] * infact[b]) % mod * infact[a - b] % mod);
           }
       }
   }

1. 范围：20组询问 1<= b<=a<=10^18, 1 <= p <= 10^5

卢卡斯定理：lucas

$$C_a^b\equiv C_{amodp}^{bmodp} * C_{a/p}^{b/p}(mod p)$$

时间复杂度：

$$O(log_p^n*p*log_p)$$

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class combination3 {
    static int p;

    static int qmi(int a, int b){
        int res = 1 % p;
        while(b != 0){
            if((b & 1) == 1)res = (int)((long)res * a % p);
            a = (int)((long) a * a % p);
            b >>= 1;
        }
        return res;
            
    }
    static int C(long a, long b){
        int res = 1;
        for(int i = 1, j = (int)a; i <= b; i++, j--){
            res = (int) ((long) res * j % p);
            res = (int) ((long) res * qmi(i, p-2) % p);
        }
        return res;
    }
    static int lucas(long a, long b){
        if(a < p && b < p){
            return C(a, b);
        }
        return (int) ((long) lucas(a/p, b/p) * C(a % p, b % p) % p);
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        while(n -- != 0){
            String[] s = br.readLine().split(" ");
            long a = Long.parseLong(s[0]);
            long b = Long.parseLong(s[1]);
            p = Integer.parseInt(s[2]);

            System.out.println(lucas(a, b));
        }
    }
}

1. 没有模除降低数量级，单纯求组合数 1≤b≤a≤5000

• 从定义出发，求：

$$C_a^b =\frac{a!}{b! * (a-b)!}$$

• 对阶乘分解质因数,有：

  因此，a!中含有的p的个数可化简为：

$$cnt = \lfloor{\frac{a}{p}}\rfloor+\lfloor{\frac{a}{p^2}}\rfloor+\lfloor{\frac{a}{p^3}}\rfloor+...$$

• 高精度乘法求结果：

  Java的大数类可以解决

  $$a!=p_0^{a_0}p_1^{a_1}...p_n^{a_n}$$

代码：

import java.math.BigInteger;
import java.util.Scanner;

public class combination04 {
    static int N = 5050;
    static int[] primes = new int[N];//记录a范围内的所有素数
    static boolean[] st = new boolean[N];
    static int cnt = 0;
    static int[] sum = new int[N];//求Cab中对应存在每一个素数的指数


    static void get_primes(int n) {//线性筛
        for (int i = 2; i <= n; i++) {
            if (!st[i]) primes[cnt++] = i;
            for (int j = 0; primes[j] <= n / i; j++) {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) break;
            }
        }
    }

    static int get(int n, int p) {//求n!中p的个数
        int res = 0;
        while(n != 0){
            res += n / p;
            n /= p;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        get_primes(a);

        for (int i = 0; i < cnt; i++) {
            int p = primes[i];
            sum[i] = get(a, p) - get(b, p) - get(a - b, p);
        }
        BigInteger res = new BigInteger("1");
        for (int i = 0; i < cnt; i++) {
            for (int j = 0; j < sum[i]; j++){
                res = res.multiply(new BigInteger(String.valueOf(primes[i])));
            }
        }
        System.out.println(res);
    }
}

卡特兰数

$$C_{2n}^n - C_{2n}^{n-1} = \frac{1}{n+1} * C_{2n}^{n}$$

适用于较多的问题：

例如：

1. 给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个

   

   触碰到红线的都是非法情况，可以在路径触碰到红线的点后进行红线的轴对称处理，那么这些非法路径将最终汇聚在(5,7)这个点上，变化后路径与变化前路径是一一对应的。

2. 一列火车 n 节车厢，依次编号为1,2,3,…,n。每节车厢有两种运动方式，进栈与出栈，问 n 节车厢出栈的可能排列方式有多少种。

代码示例：

import java.util.Scanner;

public class Catalan {
    static int mod = (int)1e9+7;
    static int qmi(int a, int b){//费马小定理 前提:p为质数
        int res = 1 % mod;
        while(b != 0){
            if((b & 1) != 0) res = (int)((long)res * a % mod);
            b >>= 1;
            a = (int)((long)a * a % mod);
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = 2 * n;
        int res = 1;
        for(int i = 1, j = a; i <= n; i++, j--){
            res = (int)((long)res * qmi(i, mod-2) % mod);//一定要注意类型转换
            res = (int)((long)res * j % mod);
        }
        res = (int)((long)res * qmi(n+1, mod-2) % mod);
        System.out.println(res);
    }
}

容斥原理

公理：（二项式定理得到 (1+x)^n）

$$C_n^0+C_n^1+C_n^2+...+C_n^n = 2^n$$ $$C_n^0-C_n^1+C_n^2-C_n^3+...+(-1)^{n-1}C_n^n = 1$$

复杂度：O(2^n)

例题：

给定一个整数 n 和 m 个不同的质数 p1, p2,…,pm。 请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

1≤m≤16 , 1≤n,pi≤10^9

复杂度：O(2^m * m) 最大2^20 一百万可接受

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class exclusion {//容斥原理
    static int N = 20;
    static int[] p = new int[N];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        String[] s = br.readLine().split(" ");
        for(int i = 0; i < m; i++){
            p[i] = Integer.parseInt(s[i]);
        }
        int res = 0;
        for(int i = 1; i < (1 << m); i++){//对i的位运算
            long t = 1;
            int cnt = 0;
            for(int j = 0; j < m; j++){
                if((i >> j & 1) != 0){//i二进制中第j位的数是否为1
                    cnt++;
                    if(t * p[j] > n){//巧妙判定界限
                        t = -1;
                        break;
                    }
                    t *= p[j];
                }
            }
            if(t != -1){
                if(cnt % 2 == 1)res += n/t;//奇数为正
                else res -= n /t;//偶数为负
            }
        }
        System.out.println(res);
    }
}

博弈论

公平组合游戏ICG

若一个游戏满足：

1. 由两名玩家交替行动
2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关
3. 不能行动的玩家判负

NIM博弈属于公平组合有熟悉，但城建的棋类游戏，比如围棋，就不是公平组合游戏，因为围棋交战双方分别智能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放一枚棋子，两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负，该游戏被称为有向图游戏

任何一个公平组合游戏都可以转化为有向图游戏，具体方法是：把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边

NIM游戏：

先手必败状态：无论如何操作，所有的剩余状态必败（走不到任何一个必败状态）

先手必胜状态：可以将剩余状态操作为某一种先手必败状态（可以走到某个必败状态）

题目：给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。

定理：

如果石子堆a[i]中，若有：

$${a_1}\oplus{a_2}\oplus{a_3}\oplus...\oplus{a_n} = 0$$

则先手必败；

若有：

$${a_1}\oplus{a_2}\oplus{a_3}\oplus...\oplus{a_n} = 1$$

则有先手必胜

证明：

(1) 有先手必败态：

$$0 \oplus 0 \oplus...\oplus = 0$$

(2)有一般情况：

$${a_1}\oplus{a_2}\oplus{a_3}\oplus...\oplus{a_n} = x ≠ 0$$

设x的最高为1位为第k位，则必存在ai的第k位为1，所以ai ^ x < ai（高于k位的ai不变，k位变为零）

于是可以从ai堆中拿走(ai - ai ^ x)个石子，剩余ai ^ x，于是有：

$${a_1}\oplus{a_2}\oplus...\oplus{a_i\oplus{x}}\oplus{a_n} = x\oplus{x} = 0$$

于是，必定存在手段使任何一种异或不为0的情况转化为异或为零的情况

(3)针对异或为0的情况，如果操作使其中一堆石子ai变为ai’，利用反证法：如果

$${a_1}\oplus{a_2}\oplus...\oplus{a_i'}\oplus{a_n} = 0$$

且

$${a_1}\oplus{a_2}\oplus...\oplus{a_i}\oplus{a_n} = 0$$

两者异或发现：

$$a_i \oplus a_i' = 0$$

二者相同，于是得出结论：异或为0的局面操作后必然会变为异或不为0的局面

综上三条，得到定理。

mex运算：

找到集合中不存在的最小的自然数

SG 函数：

在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别达到节点y1,y2,...yk，定义SG(x)为x的后继节点y1,y2,...yk的SG函数值构成的集合再执行mex(S)运算的结果，即：SG(X)=mex({SG(y1),SG(y2),...,SG(yk)})
特别地，整个有向图游戏的SG函数被定义为有向图游戏起点s的SG函数值，即SG(G)=SG(s)

SG(终点) = 0

• 先手 SG(x) = 0 必败

• 先手 SG(x) ≠ 0 必胜

SG 定理：

SG(A,B) = SG(A) ^ SG(B) 即可通过异或拆分为子情况子状态

例题：

给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。

现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

1≤n,k≤100 , 1≤si,ni≤10000

代码：

import java.util.Scanner;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main{
    static int N = 110;
    static int M = 10010;
    static int k, n;
    static int[] s = new int[N];//存储S集合
    static int[] f = new int[M];//存储sg值
    
    static int sg(int x){//记忆化搜索，妙在根据题目需求,不必把所有f[i]求出
        if(f[x] != -1)return f[x];
        Set<Integer> set = new HashSet<>();//HashSet存储
        
        for(int i = 0; i < k; i++){
            if(x >= s[i])set.add(sg(x - s[i]));//递归处理
        }
        //递归出口
        for(int i = 0; ; i++){
            if(!set.contains(i))return f[x] = i;//sg函数的具体求法
        }
    }
    
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        k = sc.nextInt();
        for(int i = 0; i < k; i++)s[i] = sc.nextInt();
        n = sc.nextInt();
        Arrays.fill(f,-1);//赋初始值为-1
        int res = 0;
        for(int i = 0; i < n; i++){
            int x = sc.nextInt();
            res ^= sg(x);
        }
        if(res != 0)System.out.println("Yes");
        else System.out.println("No");
    }
}