扩展欧几里得算法 扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中公式表述gcd(a,b)=gcd(b,a mod b)证明：a可以表示成a = kb + r，则r = a mod b假设d是a,b的一个公约数，则有d|a, d|b，而r = a - kb，因此d|r因此d是(b,a mod b)的公约数假设d 是(b,a mod b)的公约数，则d | b , d |r ，但是a = kb +r因此d也是(a,b)的公约数因此(a,b)和(b,a ...

调和级数 调和级数是由调和数列各元素相加所得的和。中世纪后期的数学家Oresme证明了所有调和级数都是发散于无穷的。但是调和级数的拉马努金和存在，且为欧拉常数积分判别法通过将调和级数的和与一个瑕积分作比较可证此级数发散。考虑右图中长方形的排列。每个长方形宽1个单位、高1/n个单位（换句话说，每个长方形的面积都是1/n），所以所有长方形的总面积就是调和级数的和： 矩形面积和： 而曲线y=1/x以下、从1到正无穷部分的面积由以下瑕积分给出： 曲线下面积： 由于这一部分面积真包含于（换言之，小于）长方形总面积，长方形的总面积也必定趋于无穷。更准确地说，这证明了： 这个方法的拓展即积分判别法。 练...

定义 斐波那契数列是一个比较简单的数列，他们有递归式f0 = 0f1 = 1fn = f(n - 1) + f(n - 2)定义 历史 斐波那契的研究文献最早由意大利天文学家卡西尼发表，卡西尼给出了关于斐波那契的一个古老的的恒等式f(n + 1)f(n - 1) = (-1) ^ n 例题 http://acm.hdu.edu.cn/showproblem.php?pid=1715Fibonacci数列，定义如下：f(1)=f(2)=1f(n)=f(n-1)+f(n-2) n>=3。计算第n项Fibonacci数值。 import java.math.BigInteger; import...

介绍 欧几里得算法又名辗转相除法，是用于快速求解最大公约数的算法 原理 两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数 实现 我们可以使用c++ 中<algorithm>头文件中的__gcd(a, b)函数来求a，b的最大公约数，也可以自己写一个程序来实现它c语言实现代码</algorithm> int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } 练习题 UVA - 11827 #include<iostream> #include<string>...

定义 同余定理是数论四大基本定理之一，在acm中常常用到，他的表达形式为a≡b (mod m)。这代表着a与b关于m同余，读作a同余于b模m 应用 同余定理常常配合其他数论算法使用，单独考察同余的地方不多，一般是对1e9+ 7求余以确保答案在32位整数范围内 练习题 https://v4t.jk1507.cn/problem.php?pid=3899 #include <stdio.h> #include <string.h> #define N 11000 #define MOD 1000000007 typedef long long LL; LL qpow(...

素数的定义 如果一个正整数p只有两个因子1和p，那么我们称这个数是素数。大于1的非素数是合数，1既不是素数也不是合数 几种判定素数的方法 一、暴力直接一次检查这个数是不是只有两个因子，这种方法的时间复杂度比较高，为根号下n，也把这种方法叫做素性测试 int is_prime(LL n) {     if(n <= 1) return 0;     LL m = floor(sqrt(n) + 0.5);     for(LL i = 2; i <= m; i++)         if(n % i == 0) return 0;     return 1; } 二、埃氏筛法这个...

背景 参加牛客网的有书共读活动(很不错的一个活动)，每周写一篇读书笔记 另外打个小广告，我的csdn博客链接：https://blog.csdn.net/DongChengRong/article/details/86744785 什么是约瑟夫问题 约瑟夫问题又被称为约瑟夫环，他起源于1世纪的一名***历史学家。他在自己的***中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是***还是被俘，最终决定***，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再***。约瑟夫...

引言 取整函数不但在数学上具有很重要的地位，在程序设计方面也同样重要，这一章讲取整函数 数学符号及C语言库函数 取整分为两种，一种是向下取整，记为 ⌊x⌋；另一种是向上取整，记为⌈x⌉;他们分别表示取比x小或者相等的最大的整数和取比x大或相等的最小的整数。在C语言中有向上取整对应着ceil(x)，向下取整对应着 floor(x) 一些性质 图中显示的是直线y = x和向下取整函数，容易看出取整函数的值都在y = x下面，不难想到向上取整函数的值都在直线上面 除此之外我们还可以证明x - 1 < ⌊x⌋ <= x <= ⌈x⌉ < x...

引言     无论是数学还是计算机科学，我们都经常用到和式，例如，数学中的泰勒级数、二项式定理，计算机中的对数组求和/差，这些都是对和式进行处理 如何表示和式     最原始的方法是把所有的数都列举出来，例如1 + 2 + 3 + 4 + 5,这是一种最原始最直观的方式，也不会因为省略某些东西而产生歧义。但是，在实际生活中这种表示方式却没有多少人用，因为当要对一个有着一千甚至是一万的数列求和时，这种表示方式过于冗长，所以通常情况下我们在式子中加上省略号，例如 1 + 2 + ... + n。这种表示方法在实际生活中经常可以看到。但对于数学来说，有时它有显得不够严谨，例如 1 + 2 + ......

学习内容 平面上的直线 问题描述 求平面上n条直线最多能界定多少个区域 分析 从小的情形开始，不难得到当n = 0时答案是1当n = 1 时答案是2当n = 2时，答案是4可是我们不能想当然的认为答案是2 ^ n，事实上，这个结论也确实是错误的我们继续探讨更大规模的问题当n = 3时，答案是7当n = 4时，答案是11我们可以发现ln = l(n - 1) + n（如果发现不了这个规律的话可以去OEIS上去）但是这种递推式的值依赖于前一个更小实例的解，如果n非常大的话我们的复杂度是O(N)的，所以肯定会超时，因此我们还需要进一步找规律，找出封闭形式的解最后我们其实可以发现ln = (n + 1...

写作背景 参加牛客送牛币活动https://www.nowcoder.com/discuss/146077?type=1&order=0&pos=3&page=1 我来分享一下我这几年参加acm的经历（或许连经验都算不上）吧 为什么选择了这个方向？ 感觉作为一名普通二本院校学生的我参加ACM就像是掉入了一个深不见底的深坑，但是有什么办法，我就是喜欢它。 推荐教材 刘汝佳的算法竞赛入门经典第二版   俗称紫书/红书 刘汝佳的算法竞赛入门经典训练指南  俗称蓝书或者白书 日本人（忘了什么名字了，四个字太难记了只记...

原文出自https://blog.csdn.net/DongChengRong/article/details/77657318，欢迎大家访问我的博客 背景        前不久参加牛客网的有书共读活动意外的获得了一本《具体数学》，对此感谢牛客。其次领书是要条件的，条件就是写读书笔记。搞ACM的都知道具体数学是本什么样的神书（也可能是我太弱了），不过没办法，规则要写那就要写，好在第一章讲递归，还在我的承受范围之内。 正文 什么是递归 既然是讲递归那么我们首先就要明白一件事，那就是什么是递归。 递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用...