文章

如何判断两条直线是否相交？

这很容易。平面直线，无非就是两种关系：相交 或 平行。因此，只需判断它们是否平行即可。而直线平行，等价于它们的斜率相等，只需分别计算出它们的斜率，即可做出判断。

但倘若我把“直线”换成“线段”呢——如何判断两条线段是否相交？

这就有些难度了。和 直线 不同，线段 是有固定长度的，即使它们所属的两条直线相交，这两条线段也不一定相交。

叙述在输出数据时，为简便起见，往往不指定输出的格式，由系统根据数据的类型采取默认的格式，但有时希望数据按指定的格式输出，如要求以十六进制或八进制形式 输出一个 整数，对输出的小数只保留两位小数等。有两种方法可以达到此目的。

1. 使用控制符的方法
2. 使用流对象的有关成员函数

所谓素数，是指恰好有两个约数的正整数。

• 埃氏筛法
• 区间筛法
• Miller-Rabin素性测试

线段树（segment tree），顾名思义， 是用来存放给定区间（segment, or interval）内对应信息的一种数据结构。与树状数组（binary indexed tree）相似，线段树也用来处理数组相应的区间查询（range query）和元素更新（update）操作。与树状数组不同的是，线段树不止可以适用于区间求和的查询，也可以进行区间最大值，区间最小值（Range Minimum/Maximum Query problem）或者区间异或值的查询。

对应于树状数组，线段树进行更新（update）的操作为O(logn)，进行区间查询（range query）的操作也为O(logn)。

求取数组中最大连续子序列和，例如给定数组为A={1， 3， -2， 4， -5}， 则最大连续子序列和为

    $_math_inline$6$math_inline_$

，即

    $_math_inline$1+3+(-2)+4=6$math_inline_$

。

方法一共有三种，复杂度分别为

    $_math_inline$O(N^2)$math_inline_$

、

    $_math_inline$O(NlgN)$math_inline_$

、

    $_math_inline$O(N)$math_inline_$

每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的质因数。如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数。而这个因数一定是一个质数。

把一个合数用质因数相乘的形式表示出来，叫做分解质因数。如30=2×3×5 。分解质因数只针对合数。

质数： 质数（prime number）又称素数，有无限个。

质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

合数： 合数指自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。与之相对的是质数，而1既不属于质数也不属于合数。最小的合数是4。其中，完全数与相亲数是以它为基础的。