初等数论四大定理

2018-04-11 Vaniot
数论，数学
费马小定理(Fermat's little theorem) 费马小定理：假假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。即$a^{p}\equiv a{\pmod {p}}$ more 证明： 法一: gcd（a，p）=1,将$1\cdot a,2\cdot a,....(p-1)\cdot a$共(p-1)个数，将他们分别除以p，余数分别为$r_{1},r_{2}......r_{p-1}$,则集合{$r_{1},r_{2}......r_{p-1}$}为{1，2，3...（p-1)}的重排列，即1,2,3,....,(p-1)在余数中恰好各出现一次，（对于 继续阅读 »

NOIP2011 Day2 计算系数：快速求组合数

2014-10-25 Xie Jingyi
数论 NOIP
题目大意 输入a, b, k, n, m，计算$a^n\times b^m\times C_k^n$模10007的余数。 分析 对于幂数的计算并不难，关键在于对组合数$C_n^k$的计算。 通常来说，组合数的计算一般是这样的：$$C_n^k=\frac{n}{k}\times\frac{n-1}{k-1}\times\ldots\times\frac{n-k+1}{1}$$ 这对于单精度的计算来说是十分快捷的，但如果要对结果取模的话就不起作用了——取模运算对于除法不成立。因此只能另辟蹊径了。 注意到加减乘法对于取模都是成立的，从而想到：能否将组合数转化成加法？ 自然而然，想到了组合恒等式：$$C_n^k=C_{n-1}^{k} 继续阅读 »

二进制的启示

2014-11-01 Xie Jingyi
NOIP
在学习数论时我们都知道：只用2的幂次可以组合出所有的正整数。这便是二进制的魅力——状态简单而又变化万千。 引子 实际算法中，常常有一些线性的但数据量特别大的问题，如区间求和、求最小值等。很多时候，为了把时间复杂度从$O(n^2)$甚至更高的地方降下来，我们需要对数据进行一些预处理，以提高计算的速度。在这其中，有很大一部分是来自二进制运算特点的启发。 目录 树状数组 RMQ LCA&树上倍增 继续阅读 »

扩展欧几里得算法

2014-10-01 Xie Jingyi
NOIP
今天开始学习数论方面的算法。这部分在NOIP中并不常出现，即使出现了也不会像高联这么难（。。。）。 什么是扩展欧几里得算法 所谓欧几里得算法，实际上就是辗转相除法——求两个数最大公约数的一种高效算法。而扩展欧几里得算法则是来源于于一类方程的解决： $$ax+by=gcd(a,b)$$ 这有点像是裴蜀定理的一般形式。和裴蜀定理类似，这类方程也有无数多个整数解。如何高效率地求得它的一组特解呢？ 代码 pascal procedure gcd_ex(a, b: longint; var d: longint; var x, y: longint); begin if b = 0 then begin 继续阅读 »