蓝桥杯AcWing学习笔记 8-1数论的学习(上)

这篇具有很好参考价值的文章主要介绍了蓝桥杯AcWing学习笔记 8-1数论的学习(上)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

蓝桥杯

我的AcWing

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

数论(上)

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

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

蓝桥杯AcWing学习笔记 8-1数论的学习(上),蓝桥杯,蓝桥杯,数据结构,算法,数论,后端

欧几里得算法代码:

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 N=P_{1}^{α_{1}}×P_{2}^{α_{2}}×...×P_{k}^{α_{k}} N=P1α1×P2α2×...×Pkαk,其中 P i P_{i} Pi 是质数,每一个 α i ≥ 0 α_{i} \geq0 αi0

蓝桥杯AcWing学习笔记 8-1数论的学习(上),蓝桥杯,蓝桥杯,数据结构,算法,数论,后端

筛法求素数——线性筛法(欧拉筛法)

O ( N ) O(N) 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; // 通过最小质因子来筛
            }
        }
    }
}

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

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

② 合数一定会被筛掉

蓝桥杯AcWing学习笔记 8-1数论的学习(上),蓝桥杯,蓝桥杯,数据结构,算法,数论,后端

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

例题

AcWing 1295. X的因子链

算术基本定理

线性筛法

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

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

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

蓝桥杯AcWing学习笔记 8-1数论的学习(上),蓝桥杯,蓝桥杯,数据结构,算法,数论,后端

排列数公式: ( α 1 + α 2 + . . . + α k ) ! α 1 ! ⋅ α 2 ! ⋅ . . . ⋅ α k ! (α_{1}+α_{2}+...+α_{k})! \over α_{1}!·α_{2}!·...·α_{k}! α1!α2!...αk!(α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的倍数,但是题中的等差数列有一部分未连续,所以我们要找到除了第一项,其余的每一项和第一项的差的最大公约数dd就是整个数列公差的最大值。

蓝桥杯AcWing学习笔记 8-1数论的学习(上),蓝桥杯,蓝桥杯,数据结构,算法,数论,后端

求项数公式: a 末 − a 首 d a_{末}-a_{首} \over d daa + 1 + 1 +1

时间复杂度 O ( N l o g N ) O(NlogN) O(NlogN)

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;
    }
}

第七届2016年蓝桥杯真题

AcWing 1223. 最大比例

C++B组第10题

最大公约数

辗转相减法

M M M个奖金构成了一个等比数列,奖金是正整数,但是比值有可能是分数;从这些等比数列挑出一部分数字,通过选出来的这些数来推断原来等比数列的比值的最大可能值是多少。

蓝桥杯AcWing学习笔记 8-1数论的学习(上),蓝桥杯,蓝桥杯,数据结构,算法,数论,后端

这题太难了,没肝动。文章来源地址https://www.toymoban.com/news/detail-795223.html

到了这里,关于蓝桥杯AcWing学习笔记 8-1数论的学习(上)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《数据结构》学习笔记

    1.算法分析的两个主要任务:正确性(不变性 + 单调性) + 复杂度。 2.复杂度分析的主要方法: 迭代:级数求和; 递归:递归跟踪 + 递推方程 猜测 + 验证 3.级数: (1)算术级数:与末项平方同阶 T ( n ) = 1 + 2 + ⋯ + n = n ( n + 1 ) 2 = O ( n 2 ) T(n) = 1 + 2 + cdots + n = frac{n(n+1)}{2} =

    2024年01月25日
    浏览(47)
  • 数据结构-学习笔记

     注意:该文章摘抄之百度,仅当做学习笔记供小白使用,若侵权请联系删除! 什么是数据结构? 数据结构是计算机存储、组织数据的方式。 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 结构包括逻辑结构和物理结构。 数据的逻辑结构包括4种  (1)集

    2024年01月23日
    浏览(53)
  • Redis数据结构学习笔记

    图文主要参考小林Coding的图解redis数据结构 除了它是内存数据库,使得所有的操作都在内存上进⾏之外,还有⼀个重要因素,它实现的数据结构,使 得我们对数据进⾏增删查改操作时,Redis 能⾼效的处理。 :::tips redisDb 结构 ,表示 Redis 数据库的结构,结构体⾥存放了指向了

    2024年02月02日
    浏览(45)
  • 数据结构学习笔记——多维数组、矩阵

    数组是由n(n≥1)个 相同数据类型 的数据元素组成的有限序列,在定义数组时,会为数组分配一个固定大小的内存空间,用来存储元素,数组在被定义后,其维度不可以被改变。 数组在确定其维度和维界后,元素的个数是固定的,所以不能进行插入和删除运算。数组中最常

    2024年02月03日
    浏览(48)
  • 【雨学习】数据结构入门---线性结构的笔记及代码实现

    数组元素类型相同,大小相等 定义:         n个节点离散分配,彼此通过指针相连,每个节点只有一个前驱节点,且只有一个后续节点         首节点前没有前驱节点,尾节点没有后续节点 专业术语:         首节点:第一个有效节点         尾节点:最后

    2024年01月23日
    浏览(53)
  • 数据结构学习笔记——二叉排序树

    查找算法中,基于树这种数据结构进行查找即为树形查找,可将其分为 二叉排序树 、 平衡二叉树 和 B树 三种树形查找方法: 二叉排序树也称为二叉查找树或二叉搜索树(注意:与二分查找的判定树不同),其中各结点值的大小关系是: 左子树根结点右子树 ,且左、右子树

    2024年02月09日
    浏览(55)
  • 区块链学习笔记(2)BTC数据结构

    1.哈希指针(hash pointers):一般的指针存储的是某个结构体在内存中的地址,哈希指针除了要保存结构体的地址外,还要保存这个结构体的哈希值。 通过哈希指针,我们不但可以找到结构体在内存中的位置,同时还可以检测出结构体的内容是否遭到了篡改。 因为我们记录了

    2023年04月16日
    浏览(53)
  • Halcon学习笔记(二)数据结构、通道+XLD

    图像(Image):图像是Halco中最基本的数据结构,用于表示二维图像。它包含了图像的像素值、尺寸、颜色模式等信息。图像可以是灰度图像(单通道图像)或彩色图像(多通道图像),颜色通道可以是RGB、HSV等。图像可以通过读取文件、采集设备或者算法生成。 区域(Regi

    2024年02月22日
    浏览(35)
  • Python学习笔记(三) 数据结构与常用方法

    数据结构是计算机内部对数据按一定的结构进行排列组织的存放,以达到快速查找,提取但目的 常见的数据结构有:列表、字典、元组、集合、双端队列、区间 通过键值对key=value的形式保存元素的一种数据结构 一种不可变的数据结构,一旦创建不能添加、删除与修改 出于数

    2024年02月04日
    浏览(50)
  • 【学习笔记】数据结构算法文档(类C语言)

    1.1.1 线性表的顺序存储表示 1.1.2 顺序表中基本操作的实现 1.1.2.1 初始化 1.1.2.2 取值 1.1.2.3 查找 1.1.2.4 插入 1.1.2.5 删除 1.1.2.6 计数 1.2.1 单链表的定义和表示 ★ 关于结点 1.2.2 单链表基本操作的实现 1.2.2.1 初始化 1.2.2.2 取值 1.2.2.3 查找 1.2.2.4 插入 1.2.2.5 删除 1.2.2.6 前插法创建单

    2024年02月07日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包