number_theory

最近看数论，转头重新思考了这题，参考了下论文和lrj的黑书，重新证明一遍，做个笔记。 例题：HDOJ 1792 A New Change Problem 题意：给定A和B，A和B互质，求最大不能组合数，和不能组合数的个数。 基础知识： $$\gcd(A, B) = 1 \Rightarrow \operatorname{lcm}(A, B) = AB$$ 剩余类，把所有整数划分成$m$个等价类，每个等价类由相互同余的整数组成 任何数分成$m$个剩余类，分别为 $mk，mk+1，mk+2，\cdots，mk+(m-1)$ 分别记为$\{0(\mod m)\}，\{1(\mod m)\}$ 而$n$的倍数肯定分布在这$m$个剩余类中 因为$\gcd(m，n)=1$，所以每个剩余类中都有一些数是$n$的倍数，并且是平均分配它的旁证，可见HDOJ 1222 Wolf and Rabbit 设 $k_{min} = \min \{ k \mid nk \in \{i (\mod m)\} \},~ i \in [0, m)$ 则 $nk_{min}$ 是$\{i (mod m)\}$中$n$的最小倍数。特别的，$nm \in \{0 (\mod m)\}$ $nk_{min}$ 是个标志，它表明$\{i (\mod m)\}$中$nk_{min}$ 后面所有数，即$nk_{min} + jm$必定都能被组合出来 那也说明最大不能组合数必定小于$nk_{min}$ 我们开始寻找$\max\{ nk_{min} \}$ $\operatorname{lcm}(m, n) = mn$，所以很明显$(m-1)n$是最大的...

当 $\gcd(m, n) = 1$时，我们称 $m$和$n$互素。 约定用 $m\bot n$来表示两者互素。 $$m / \gcd(m, n) ;\bot; n / \gcd(m, n)$$ 由 gcd和素数序列的关系我们可以得出 $$k \bot m \text{ and } k \bot n \Leftrightarrow k \bot mn$$ 书上看到一种很好玩的一种构造算法。 用来构造所有具有 $m\bot n$的非负分数 $m/n$集合，称为Stem-Brocot tree。 建树思想是： 从两个分数$（0/1， 1/0）$开始，重复以下操作，在两个邻接的分数 $m/n$和 $m'/n'$之间插入 $(m+m')/(n+n')$。 这颗树构造能保证相同分数不会出现两次，基于以下事实： 如果在任何构造阶段 $m/n$和 $m'/n'$是相继的分数，则有 $m’n - mn' = 1$ 证明： 开始时，$11 - 00 = 1$满足条件，计算出中间值 $(m+m')/(n+n')$后， $ \begin{array}{l} (m + m')n - m(n + n') = 1 ;\\ m'(n + n') - (m + m')n' = 1 ; \end{array} $...

$$n^{n/2} <= n! <= \frac{(n+1)^n}{2^n}$$ 这个公式说明阶乘是以指数律增长。 对于大的$n$，我们能用Stirling公式来精确近似$n!$。 $$n!\sim \sqrt{2\pi n}\left (\frac{n}{2} \right)^n$$ 误差是 $\frac{1}{12n}$。 $$ \begin{array}{|c|c|c|} & 1;2;3;4;5;6;7;8;9;10 & \text {powers of 2} \\ \hline \text {divisible by 2} & ;;x;;;x;;;x;;;x;;;x & 5=\left \lfloor 10/2 \right \rfloor\\ \text {divisible by 4} & ;;;;;;x;;;;;;;;x;;;; & 2= \left \lfloor 10/4 \right \rfloor\\ \text {divisible by 8} & ;;;;;;;;;;;;;;;;x;;;; & 1 = \left \lfloor 10/8 \right \rfloor\\ \hline \textbf {powers of 2} & \mathbf{0;1;0;2;0;1;0;3;0;1} & \mathbf{8} \end{array} $$...

存在无限多个素数，欧几里德递归证明： $$P_n = P_1P_2\cdots P_{n-1} + 1, (n>=1) $$ 前 $n-1个$素数中没有能除尽 $P_n$的，因为都每个能除尽 $P_{n-1}$。 形如：$2^p-1$ （$p$是素数）的数称为Mersenne numbers，中文名为梅森数 如果该梅森数也是素数的话，就叫梅森素数。 如果 $n$是合数，则数 $2^n-1$不可能是素数。 证明为：$2^{km} - 1 = (2^m -1)(2^{m(k-1)} + 2^{m(k-2)} + \cdots + 1)$ 但当 $p$是素数时，$2^p -1$不总是素数。 如最小的非梅森数 $2^{11} -1 = 2047 = 23*89$ http://acm.zju.edu.cn/show_problem.php?pid=2400 有个渐近公式，第 $k$个素数$P_k \approx k \ln k$ 这意味着当$k\rightarrow \infty , \frac{P_k}{k \ln k} \rightarrow 1$ 则类似的可以推出 $\pi (x)$表示不超过 $x$的素数个数，$\pi (x) \approx \frac{x}{\ln k}$ 当 $n$或 $x$趋向无穷大时，有更精确的估计函数。 $$ \begin{array}{ll} \ln x - \frac{3}{2} <, \frac{x}{\pi (x))} <, \ln x - \frac{1}{2}, &\text{ for } x>=67; \\ n(\ln n + \ln \ln n -\frac{3}{2}) <, P_n <, n(\ln n + \ln \ln n - \frac{1}{2}), & \text{ for } n>=20; \end{array} $$...

任何正整数$n$都能记为素数乘积。 $$n = p_1p_2\cdots p_m = \prod pk\ (1<=k<=m, p1<=\cdots<=pm) $$ 而且这个展开序列是唯一的。 假定一个数$m$可以用素数序列$<m1,m2,…>$表示 $k = mn \Leftrightarrow k_p = m_p + n_p$，对所有的p 而 $m/n \Leftrightarrow mp <= np$ ，对所有的p 那就可知 $k = gcd(m, n) \Leftrightarrow kp = min(mp, np)$ ，对所有的p $k = lcm(m, n) \Leftrightarrow kp = max(mp, np)$ ，对所有的p 如果素数$p$能除尽$mn$，则根据因子分解定理，一定有$p/m$或$p/n$，或者两者都能。但是合数就不行了。

最熟悉的一个概念，最大公约数gcd，$k/m$ 表示$k$能除尽$m$ 注意“$k$能除尽$m$”和“$m$是$k$的倍数”并不完全一样，如$k=0$ $gcd(m, n) = max\left \{k \mid k/m\ and\ k/n \right \};$ ① 欧几里德算法的递归形式： $gcd(0, n) = n;$ $gcd(m, n) = gcd(n%m, m); m > 0$ ② 还有一种扩展形式： $xm + yn = gcd(m, n);$ 这个x，y得出有个很美妙的递归求法。 假定 $n>m>=0，x_1m + y_1n = gcd(m, n);$ 1）当$m=0$时，$x_1=0，y_1=1$是它其中的一组可能解。 2）假设 $r=n%m$，则有 $gcd(r, m) = x_2r + y_2m;$ 根据②可知 $gcd(r, m) = gcd(m, n);$ 则有 $x_1m + y_1n = x_2r + y_2m;$ ③...