本文最后更新于2021年11月3日,已超过 1 个月没更新!

第四讲 数学知识

质数

试除法判定质数

import java.util.*;

//一个数的因数都是成对出现的:例如12的因数有3和4,2和6
// 所以我们可以只枚举较小的那一个,即根下n,假设较小的为d,较大的为n/d;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt();
            System.out.println(isPrime(n) ? "Yes" : "No");
        }
    }

    // 不建议使用 i <= Math.sqrt(n) 速度慢
    // 不建议使用 i * i <= n 因为有溢出概率 
    private static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i <= n / i; ++ i) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

分解质因数

import java.util.*;

// 给定 n 个正整数 ai,将每个数分解质因数,
// 并按照质因数从小到大的顺序输出每个质因数的底数和指数。
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt();
            List<int[]> list = devide(n);
            for (int[] a : list) {
                System.out.println(a[0] + " " + a[1]);
            }
            System.out.println();
        }
    }

    // n 中最多只包含一个大于sqrt(n)的质因子
    private static List<int[]> devide(int n) {
        List<int[]> list = new ArrayList<>();
        for (int i = 2; i <= n / i; ++ i) {
            if (n % i == 0) {
                int s = 0;
                while (n % i == 0) {
                    n /= i;
                    ++ s;
                }
                list.add(new int[]{i, s});
            }
        }
        if (n > 1) list.add(new int[]{n, 1});
        return list;
    }
}

筛质数

import java.util.*;

// 给定一个正整数 n,请你求出 1 ∼ n 中质数的个数。
// 质数定理:1 ~ n 中有 n / In(n) 个质数
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(getPrimesNum3(n));
    }

    // 朴素筛法O(nlogn)
    // 遍历 1 ~ n 删除掉遍历到的所有数的所有倍数,最后留下的就是所有质数
    public static int getPrimesNum1(int n) {
        boolean[] st = new boolean[n + 1];
        int cnt = 0;
        for (int i = 2; i <= n; ++ i) {
            if (!st[i]) cnt ++;
            for (int j = i + i; j <= n; j += i) st[j] = true; // 删除掉倍数
        }
        return cnt;
    }

    // 埃式筛法O(nlog(logn))
    // 优化 ️-> 遍历1 ~ n 删除掉遍历到的质数的所有倍数,最后留下的就是所有质数
    public static int getPrimesNum2(int n) {
        boolean[] st = new boolean[n + 1];
        int cnt = 0;
        for (int i = 2; i <= n; ++ i) {
            if (!st[i]) {
                cnt ++;
                for (int j = i + i; j <= n; j += i) st[j] = true; // 删除掉倍数
            }
        }
        return cnt;
    }

    // 线性筛法O(n) n = 1e7的时候基本比埃式筛法快一倍
    // n 只会被最小质因子筛掉
    // 1. i % primes[j] == 0, pj定为i最小质因子,primes[j]也一定为primes[j] * i最小质因子
    // 2. i % primes[j] != 0, pj定小于i的所有质因子,所以primes[j]也为primes[j] * i最小质因子
    public static int getPrimesNum3(int n) {
        int[] primes = new int[n + 1];
        boolean[] st = new boolean[n + 1];
        int cnt = 0;
        for (int i = 2; i <= n; ++ i) {
            if (!st[i]) primes[cnt ++] = i;
            for (int j = 0; primes[j] <= n / i; ++ j) {
                //对于任意一个合数x,假设primes[j]为x最小质因子,当i < x/primes[j]时,一定会被筛掉
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) break; // primes[j] 一定是最小质因数
            }
        }
        return cnt;
    }
}

约数

试除法求约数

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt();
            for (int x : getDivisors(n)) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
    }

    // 同试除法求质数
    public static List<Integer> getDivisors(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n / i; ++ i) {
            if (n % i == 0) {
                list.add(i);
                if (i != n / i) list.add(n / i); // 一对约数要是相同则只加一个
            }
        }
        Collections.sort(list);
        return list;
    }
}

约数个数

$$
n = p^{α_1}_1 + p^{α_2}_2 + p^{α_3}_3 + ...... + p^{α_k}_k \
ans = (α_1 + 1)(α_2 + 1)(α_3 + 1)......(α_k + 1)\
$$

import java.util.*;

public class Main{
    public static void main(String[] args) {
        int mod = (int)(1e9 + 7);
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

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

        long ans = 1;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            ans = ans * (entry.getValue() + 1) % mod;
        }
        System.out.println(ans);
    }
}

约数之和

$$
ans = (p_1^0 + p_1^1 + ... + p_1^{α1}) + (p_2^0 + p_2^1 + ... + p_2^{α_2}) + ...... + (p_k^0 + p_k^1 + ... + p_k^{α_k})\
= \sum
{i=1}^k{p_i^0 + p_i^1 + ... + p_i^{α_1}}
$$

import java.util.*;

public class Main{
    public static void main(String[] args) {
        int mod = (int)(1e9 + 7);
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

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

        long ans = 1;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int p = entry.getKey(), k = entry.getValue();
            long v = 1;
            while (k -- > 0) v = (v * p + 1) % mod;
            ans = (ans * v) % mod;
        }
        System.out.println(ans);
    }
}

最大公约数

import java.util.*;

public class Main{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n -- > 0) {
            int a = sc.nextInt(), b = sc.nextInt();
            System.out.println(gcd(a, b));
        }
    }
    // 最大公约数 欧基里德算法(辗转相除法)
    // (a, b)的最大公约数 == (b, a % b)的最大公约数
    // 原理:
    // a % b = a - (a / b) * b 
    // d能整除b d能整除 a % b
    // 则:
    // a / d = (a - (a / b) * b + (a / b) * b) / d = (a % b) / d + (a / b) * (b / d) 显然也可整除
    // 故结论成立
    // a 和 0 的最大公约数是 a
    private static int gcd (int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

快速幂

快速幂

import java.util.*;

// 给定 n 组 ai,bi,pi,对于每组数据,求出 ai ^ bi mod pi 的值。
public class Main{


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int x = sc.nextInt(), n = sc.nextInt(), mod = sc.nextInt();
            System.out.println(quickPow(x, n, mod));
        }
    }

    // 快速幂(反复平方法)
    // logn时间复杂度
    public static int quickPow(int x, int n, int mod) {
        long res = 1;
        long a = (long)x;
        while (n != 0) {
            if ((n & 1) == 1) res = (res * a) % mod;
            n >>= 1;
            a = (a * a) % mod;
        }
        return (int)res;
    }
}

求组合数

求组合数 I

$$
C_a^b从a个苹果中选出b个的方案数\
C_a^b = C_{a-1}^b + C_{a-1}^{b-1}
$$

import java.util.*;

// 数据范围
// 1 ≤ n ≤10000,
// 1 ≤ b ≤ a ≤2000
public class Main{
    // 递推求出所有组合数
    static int N = 2010, mod = (int)(1e9 + 7);
    static int[][] c = new int[N][N];
    public 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;
             }
         }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        init();
        int t = sc.nextInt();
        while (t -- > 0) {
            int i = sc.nextInt(), j = sc.nextInt();
            System.out.println(c[i][j]);
        }
    }
}

求组合数 II

求组合数 III

求组合数 IV


Try and fail, but don't fail to try.