acm

中国邮递员问题 1962年有管梅谷先生提出中国邮递员问题（简称CPP）。一个邮递员从邮局出发，要走完他所管辖的每一条街道，可重复走一条街道，然后返回邮局。任何选择一条尽可能短的路线。 这个问题可以转化为：给定一个具有非负权的赋权图G， 用添加重复边的方法求G的一个Euler赋权母图G*，使得尽可能小。 求G*的Euler 环游。 人们也开始关注另一类似问题，旅行商问题（简称TSP）。TSP是点路优化问题，它是NPC的。而CPP是弧路优化问题，该问题有几种变形，与加权图奇点的最小完全匹配或网络流等价，有多项式算法。1 欧拉图 图G中经过每条边一次并且仅一次的回路称作欧拉回路。存在欧拉回路的图称为欧拉图。 无向图欧拉图判定 无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。 有向图欧拉图判定 有向图G为欧拉图，当且仅当G的基图2连通，且所有顶点的入度等于出度。 欧拉回路性质 性质1　设C是欧拉图G中的一个简单回路，将C中的边从图G中删去得到一个新的图G’，则G’的每一个极大连通子图都有一条欧拉回路。 性质2　设C1、C2是图G的两个没有公共边，但有至少一个公共顶点的简单回路，我们可以将它们合并成一个新的简单回路C’。 欧拉回路算法 在图G中任意找一个回路C； 将图G中属于回路C的边删除； 在残留图的各极大连通子图中分别寻找欧拉回路； 将各极大连通子图的欧拉回路合并到C中得到图G的欧拉回路。 由于该算法执行过程中每条边最多访问两次，因此该算法的时间复杂度为O(|E|)。 如果使用递归形式，得注意|E|的问题。使用非递归形式防止栈溢出。 如果图 是有向图，我们仍然可以使用以上算法。 http://acm.hdu.edu.cn/showproblem.php?pid=1116 有向图欧拉图和半欧拉图判定 http://acm.pku.edu.cn/JudgeOnline/problem?id=2337 输出路径 中国邮递员问题① 一个邮递员从邮局出发，要走完他所管辖的每一条街道，可重复走一条街道，然后返回邮局。所有街道都是双向通行的，且每条街道都有一个长度值。任何选择一条尽可能短的路线。 分析 双向连通，即给定无向图G。 如果G不连通，则无解。 如果G是欧拉图，则显然欧拉回路就是最优路线。 如果G连通，但不是欧拉图，说明图中有奇点3。奇点都是成对出现的，证明从略。 对于最简单情况，即2个奇点，设（u，v）。我们可以在G中对（u，v）求最短路径R，构造出新图G’ = G ∪ R。此时G’就是欧拉图。...

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

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