蓝桥杯AcWing学习笔记 8-1数论的学习（上）

蓝桥杯

我的AcWing

题目及图片来自蓝桥杯C++ AB组辅导课

数论（上）

蓝桥杯省赛中考的数论不是很多，这里讲几个蓝桥杯常考的知识点。

欧几里得算法——辗转相除法

欧几里得算法代码：

import java.util.Scanner ;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt();
        System.out.println(gcd(a, b));
    }

    private static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}

算术基本定理

就是因式分解的定理，所有的整数都可以唯一分解成若干个质因子乘积的形式：

$N=P_{1}^{α_{1}}×P_{2}^{α_{2}}×...×P_{k}^{α_{k}}$ ，其中 $P_{i}$ 是质数，每一个 $α_{i} \geq0$

筛法求素数——线性筛法（欧拉筛法）

在 $O (N)$ 的时间复杂度内，求出来1 ~ n中所有的质数，以及每一个数的最小质因子。

import java.util.Scanner ;

public class Main {

    static final int N = 1000010;
    static int[] primes = new int[N]; // 存所有的质数
    static int cnt; // 存质数的个数
    static boolean[] st = new boolean[N]; // 当前数有没有被筛过 0没有被筛过 1表示筛过

    public static void main(String[] args) {
        get_primes(100000);
        
        for (int i = 0; i < 20; i++) System.out.println(primes[i]); // 输出100000的前20个质数
    }

    private 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] * i <= n; j++) {
                /*
                  因为prime中素数是递增的，所以如果i%prime[j]!=0代表i的最小质因数还没有找到，
                  即i的最小质因数大于prime[j]
                  也就是说prime[j]就是i*prime[j]的最小质因数，于是i*prime[j]被它的最小质因数筛掉了
                */
                st[primes[j] * i] = true; // 把质数的i倍筛掉
                /*
                  如果当i%prime[j]==0时，代表i的最小质因数是prime[j]，
                  那么i*prime[j+k](k>0)这个合数的最小质因数就不是prime[j+k]而是prime[j]了
                  所以i*prime[j+k]应该被prime[j]筛掉，而不是后续的prime[j+k]，于是在此时break
                */
                if (i % primes[j] == 0) break; // 通过最小质因子来筛
            }
        }
    }
}

注释中的两段解释参考博客线性筛（欧拉筛）——算法解析

① 筛掉的一定是合数，且一定是用其最小质因子筛的

② 合数一定会被筛掉

这样我们就可以把所有质数找出来，而且每个和数只会被最小质因子筛，所以每个和数只会被筛一次，所以整个算法的时间复杂度为 $O (N)$

例题

AcWing 1295. X的因子链

算术基本定理

线性筛法

题意有点绕，通俗来讲就是给我们任意一个正整数 $X$ ，我们可以求一下 $X$ 所有的约数： $d_{1},d_{2}...d_{k}$ ，然后我们要从中挑出来一些严格单调递增的数，使得每一项都是它前一项的倍数： $a_{1}<a_{2}<...<a_{t}$ $a_{i}|a_{i+1})$ ，然后问我们可以挑出来的序列的最大长度是多少，以及有多少个满足条件的单调递增的序列？

每一项必然满足： $a_{i+1} = a_{i}·P(P是倍数且>1)$ ，每一个后一项都等于前一项乘上一个倍数，那么我们要想让整个序列最长的话，要尽可能让倍数最小，最小只能小到质数，因为小到质数就不能再分了，因此就可以用我们上边的算术基本定理了，假设 $X$ 分解质因数的结果： $X=P_{1}^{α_{1}}×P_{2}^{α_{2}}×...×P_{k}^{α_{k}}$ ，我们可以发现一共有 $α_{1}+α_{2}+...+α_{k}$ 个质因子，因此我们每一次后一项要比前一项至少要多一个倍数，每一次的倍数必然是一个质数，必然是在 $X$ 当中的某一个质因子，所以序列的最大长度就是 $α_{1}+α_{2}+...+α_{k}$

那么如何求这样序列的个数呢？先做一个映射，我们不存数的本身，我们存数的增量，原序列是 $a_{1},a_{2}...a_{t}$ ，映射的序列是： $a_{1}$ , $a_{2}\over a_{1}$ , $a_{3}\over a_{2}$ $...$ $a_{t}\over a_{t-1}$ ，这两个序列是一一对应的，给我们第一个序列就可以求第二个序列，在第二个序列中每一个数都是 $X$ 的质因子，因此序列个数就是 $X$ 所有质因子的排列数。

排列数公式： $(α_{1}+α_{2}+...+α_{k})! \over α_{1}!·α_{2}!·...·α_{k}!$ ，也被称为多重集合的排列数问题，这样就避免了重复情况。

我们分解质因数就用线性筛法来解。

import java.util.Scanner ;

public class Main {

    static final int N = (1 << 20) + 10;
    static int[] primes = new int[N]; // 存所有的质数
    static int cnt; // 存质数的个数
    static int[] minp = new int[N]; // 存最小质因子
    static boolean[] st = new boolean[N]; // 当前数有没有被筛过

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        get_primes(N - 1);

        int[] fact = new int[30]; // 记录因子
        int[] sum = new int[N]; // 存因子个数

        while (sc.hasNext()) {
            int x = sc.nextInt();
            int k = 0, total = 0;
            while (x > 1) {
                int p = minp[x];
                fact[k] = p;
                sum[k] = 0;
                while (x % p == 0) { // 分解质因数
                    x /= p;
                    sum[k]++;
                    total++;
                }
                k++;
            }

            long res = 1;
            for (int i = 1; i <= total; i++) res *= i; // 求total的阶乘
            for (int i = 0; i < k; i++) { // 多重集合的排列数
                for (int j = 1; j <= sum[i]; j++) {
                    res /= j;
                }
            }

            System.out.println(total + " " + res);
        }
    }

    private static void get_primes(int n) {
        for (int i = 2; i <= n; i++) {
            if (!st[i]) {
                minp[i] = i; // 因为i是质数 最小质因子就是它本身
                primes[cnt++] = i;
            }
            for (int j = 0; primes[j] * i <= n; j++) {
                int t = primes[j] * i;
                st[t] = true;
                minp[t] = primes[j];
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) break;
            }
        }
    }
}

第十届2019年蓝桥杯真题

AcWing 1246. 等差数列

C++B组第8题

最大公约数

欧几里得算法

在等差数列中，每一项与第一项的差一定是公差d的倍数，但是题中的等差数列有一部分未连续，所以我们要找到除了第一项，其余的每一项和第一项的差的最大公约数d，d就是整个数列公差的最大值。

求项数公式： $a_{末}-a_{首} \over d$ $+ 1$

时间复杂度 $O (Nl o g N)$

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    
    static final int N = 100010;
    static int[] a = new int[N];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        Arrays.sort(a, 0, n);
        
        int d = 0;
        for (int i = 1; i < n; i++) d = gcd(d, a[i] - a[0]); // 求最大公约数
        
        if (d == 0) System.out.print(n); // 表示所有项都相同
        else System.out.print((a[n - 1] - a[0]) / d + 1); // 求项数公式
    }

    private static int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}