Tag: 数论

卢卡斯定理

摘要: 求组合数的代码模板和例题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 卢卡斯定理设 p 是一个素数,将 m 和 n 写成 p 进制数: n = a_{0} + a_{1}p + a_{2

力扣LCP14-切分数组

摘要: LCP14,分解质因数+哈希表优化DP 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文看一个分解质因数与动态规划结合的题。直接写出动态规划算法比较简单,但难点在于如何用分解质因数进行优化

力扣1390-四因数

摘要: 力扣 1390,算数基本定理与素数筛 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文看一个数论题,属于算数基本定理的应用,当然本题也可以用枚举的方法解决。 题目 1390. 四因

力扣866-回文素数

摘要: 力扣 866-回文素数。构造回文+素性测试。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们看一个题,算是素性测试的应用。此外本题枚举回文串的过程也是一个难点,值得学习。 题目 86

力扣952-按公因数计算最大组件大小

摘要: 本文详细拆解 力扣952-按公因数计算最大组件大小。分解质因数+并查集 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来看一个数论与并查集结合的问题,综合性比较强。 $1 题

力扣372-超级次方

摘要: 力扣 372:快速幂、扩展欧拉定理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 题目 372. 超级次方 你的任务是计算 ab 对 1337 取模,a 是一个正整数,b 是一个非常大的正

【分治】A的B次方的所有约数之和

摘要: 综合题:分治+分解质因数+模下快速幂 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 分治 中,我们系统学习了分治算法,了解了分治的思想和流程,以及研究分治算法时间复杂度的主定理,然后

具体数学

摘要: 《具体数学》,算法分析的数学基础 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 书名《具体数学》 豆瓣链接: 具体数学 : 计算机科学基础 时间: 2013 具体数学 递归问题

初等数论知识体系

摘要: 介绍两本初等数论的书 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 介绍两本初等数论的书书,其中第一本与编程中常见的知识,第二本有一些应用的内容。有需要的时候可以参考。 (1) 初等数论 作

leetcode数学题目汇总

摘要: 本文系统梳理了数学相关的算法。并汇总了 leetcode 上的相关的题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文总结了力扣上 2000 题以内的关于数学的 49 道题。将场景相

取模与分数取整

摘要: 分数取整与取模的关系,约瑟夫环问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们来看一下在数学算法中常见的分数取整问题,以及分数取整与取模的关系。我们直接给出结论公式,然后详细拆解

素数筛-对阶乘分解质因数

摘要: 如何对阶乘进行分解质因数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我看一个素数筛的应用问题:对阶乘分解质因数,以及后续应用,关于素数筛的算法和代码参考 素数筛。 对阶乘分解质因数给

【DP难题】力扣920-播放列表数量

无串线性 dp 容斥原理 交集 = 并集 - 差集 组合数学解法:官方题解,并没有看懂 求有限制的排列个数问题 生成函数和中国剩余定理的应用 $1 题目题目链接920. 播放列表的数量 题目描述你的音乐播放器里有 N 首不同的歌,在旅途中,你的旅伴想要听 L 首歌(不一定不同,即,允许歌曲重复)。请你为她按如下规则创建一个播放列表: 每首歌至少播放一次。一首歌只有在其他 K 首歌播放完

同余

摘要: 本文介绍同余的算法原理和代码模板、以及几道相关题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文详细研究同余以及相关的定理。主要内容如下: 同余的定义 同余类与剩余系 费马小

约数

摘要: 本文介绍约数的定理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文详细研究约数以及相关的定理。主要内容如下: 约数的定义 算术基本定理 算术基本定理的推论 求正约数集合 N :

力扣365-水壶问题

摘要: 本文详细拆解 力扣365-水壶问题,核心是隐式图搜索和裴蜀定理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来看一个数学问题,本题可以列出不定方程,可以通过数论中的裴蜀定理

素数筛

摘要: 本文介绍素数筛的算法原理和代码模板、以及几道相关题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文详细研究素数筛。首先以力扣第 204 题为模板题学习埃氏筛和线性筛,然后讨论素

最大公约数算法以及C++17组件

摘要: 本文介绍最大公约数算法的实现、C++17 相应的组件、以及几道相关题目 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 最大公约数是数论中最基础的内容,在算法中也经常见到关于最大公约数相关的问

组合数学4-容斥原理,鸽巢原理

摘要: 组合数学:容斥原理、鸽巢原理 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在 组合数学1-排列组合 中我们详细梳理了组合数学的基本模型以及相关公式;在 组合数学2-母函数,递推关系 中我们