关于数论中的互质数的最大不能组合数

最近看数论,转头重新思考了这题,参考了下论文和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$是最大的...

August 30, 2007 · 1 min · HuangWei

Number Theory 4.5 Relative Primality

当 $\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} $...

August 24, 2007 · 1 min · HuangWei

Number Theory 4.4 Factorial Factors

$$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} $$...

August 23, 2007 · 1 min · HuangWei

Number Theory 4.3 Prime Examples

存在无限多个素数,欧几里德递归证明: $$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} $$...

August 22, 2007 · 1 min · HuangWei

Number Theory 4.2 Primes

任何正整数$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$,或者两者都能。但是合数就不行了。

August 21, 2007 · 1 min · HuangWei

Number Theory 4.1 Divisibility

最熟悉的一个概念,最大公约数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;$ ③...

August 18, 2007 · 1 min · HuangWei