Tag: 数论

2023
数组合数学

卢卡斯定理

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

算法疑难杂症

力扣LCP14-切分数组

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

算法leetcode

力扣1390-四因数

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

算法leetcode

力扣866-回文素数

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

算法leetcode

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

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

算法leetcode

力扣372-超级次方

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

2022
算法疑难杂症

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

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

算法算法分析

具体数学

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

数数论

初等数论知识体系

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

2021
算法数学算法

leetcode数学题目汇总

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

2020
算法数学算法

取模与分数取整

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

数数论

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

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

算法leetcode

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

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

数数论

同余

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

数数论

约数

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

算法leetcode

力扣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-母函数,递推关系 中我们