国家集训队2009论文集slide.pdf

欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 总总总结结结 感感感谢谢谢 欧欧欧几几几里里里得得得算算算法法法的的的应应应用用用 金斌 江苏省常州高级中学 2009 年 1 月 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 总总总结结结 感感感谢谢谢 总总总览览览 论论论文文文内内内容容容 1 欧几里得算法 辗转相除 2 拓展欧几里得算法 模线性方程 组 3 另类欧几里得算法 4 连分数与Pell方程 5 例题 Wifi Planet TopCoder SRM 410 HARD 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 总总总结结结 感感感谢谢谢 总总总览览览 论论论文文文内内内容容容 1 欧几里得算法 辗转相除 2 拓展欧几里得算法 模线性方程 组 3 另类欧几里得算法 4 连分数与Pell方程 5 例题 Wifi Planet TopCoder SRM 410 HARD 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 总总总结结结 感感感谢谢谢 总总总览览览 论论论文文文内内内容容容 1 欧几里得算法 辗转相除 2 拓展欧几里得算法 模线性方程 组 3 另类欧几里得算法 4 连分数与Pell方程 5 例题 Wifi Planet TopCoder SRM 410 HARD 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 总总总结结结 感感感谢谢谢 总总总览览览 论论论文文文内内内容容容 1 欧几里得算法 辗转相除 2 拓展欧几里得算法 模线性方程 组 3 另类欧几里得算法 4 连分数与Pell方程 5 例题 Wifi Planet TopCoder SRM 410 HARD 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 总总总结结结 感感感谢谢谢 总总总览览览 论论论文文文内内内容容容 1 欧几里得算法 辗转相除 2 拓展欧几里得算法 模线性方程 组 3 另类欧几里得算法 4 连分数与Pell方程 5 例题 Wifi Planet TopCoder SRM 410 HARD 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 总总总结结结 感感感谢谢谢 总总总览览览 论论论文文文内内内容容容 1 欧几里得算法 辗转相除 2 拓展欧几里得算法 模线性方程 组 3 另类欧几里得算法 4 连分数与Pell方程 5 例题 Wifi Planet TopCoder SRM 410 HARD 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 总总总结结结 感感感谢谢谢 总总总览览览 论论论文文文内内内容容容 1 欧几里得算法 辗转相除 2 拓展欧几里得算法 模线性方程 组 3 另类欧几里得算法 一道例题 4 连分数与Pell方程 5 例题 Wifi Planet TopCoder SRM 410 HARD 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 辗辗辗转转转相相相除除除 分分分析析析 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 总总总结结结 感感感谢谢谢 辗辗辗转转转相相相除除除 伪伪伪代代代码码码 由于是数论的最基本算法 所以这里我直接给出伪代码 伪伪伪代代代码码码 Input x 0 y 0 Output the greatest common divisor of x and y 1 while y 0 do 2 t x mod y 3 x y 4 y t 5 end while 6 return x 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 辗辗辗转转转相相相除除除 分分分析析析 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 总总总结结结 感感感谢谢谢 辗辗辗转转转相相相除除除 伪伪伪代代代码码码 由于是数论的最基本算法 所以这里我直接给出伪代码 伪伪伪代代代码码码 Input x 0 y 0 Output the greatest common divisor of x and y 1 while y 0 do 2 t x mod y 3 x y 4 y t 5 end while 6 return x 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 辗辗辗转转转相相相除除除 分分分析析析 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 总总总结结结 感感感谢谢谢 欧欧欧几几几里里里得得得算算算法法法 复复复杂杂杂度度度分分分析析析 对于任意两个数a b满足a b 0 我们考虑如下这个语句 的效果 a a mod b 1 如果b a 2 则a mod b a 2 则a mod b a b b 0 我们考虑如下这个语句 的效果 a a mod b 1 如果b a 2 则a mod b a 2 则a mod b a b b 0 我们考虑如下这个语句 的效果 a a mod b 1 如果b a 2 则a mod b a 2 则a mod b a b b 0 我们考虑如下这个语句 的效果 a a mod b 1 如果b a 2 则a mod b a 2 则a mod b a b OE 则容易证明 OAB AOB 做A关 于E的对称点A 易得 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 开开开阔阔阔视视视野野野 题题题目目目 分分分析析析 Wifi Planet 总总总结结结 感感感谢谢谢 二二二维维维欧欧欧几几几里里里得得得算算算法法法 分分分析析析 这里我们重申上面的约定 a b 下面请看下图 O B A E C D 如果此时 OA OE 则容易证明 OAB AOB 做A关 于E的对称点A 易得 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 开开开阔阔阔视视视野野野 题题题目目目 分分分析析析 Wifi Planet 总总总结结结 感感感谢谢谢 二二二维维维欧欧欧几几几里里里得得得算算算法法法 分分分析析析 这里我们重申上面的约定 a b 下面请看下图 O B A E C D 如果此时 OA OE 则容易证明 OAB AOB 做A关 于E的对称点A 易得 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 开开开阔阔阔视视视野野野 题题题目目目 分分分析析析 Wifi Planet 总总总结结结 感感感谢谢谢 二二二维维维欧欧欧几几几里里里得得得算算算法法法 分分分析析析 这里我们重申上面的约定 a b 下面请看下图 O B A E C D 如果此时 OA OE 则容易证明 OAB AOB 做A关 于E的对称点A 易得 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 开开开阔阔阔视视视野野野 题题题目目目 分分分析析析 Wifi Planet 总总总结结结 感感感谢谢谢 二二二维维维欧欧欧几几几里里里得得得算算算法法法 分分分析析析 这里我们重申上面的约定 a b 下面请看下图 O B A E C D 如果 CE AOB Proof 直接可以证明 DCB AOB CBO AOB 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 开开开阔阔阔视视视野野野 题题题目目目 分分分析析析 Wifi Planet 总总总结结结 感感感谢谢谢 二二二维维维欧欧欧几几几里里里得得得算算算法法法 分分分析析析 这里我们重申上面的约定 a b 下面请看下图 O B A E C D 综上 这种变换保持着向量夹角增加 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 开开开阔阔阔视视视野野野 题题题目目目 分分分析析析 Wifi Planet 总总总结结结 感感感谢谢谢 二二二维维维欧欧欧几几几里里里得得得算算算法法法 分分分析析析 所以一个基于欧几里得算法的算法就成型了 每次用二次函 数计算上面的k值 之后进行变换 直到夹角超过 3 限于知识水平 这个算法的确切复杂度我不能给出 但是根 据实验结果 基本能在几步之内结束 应该是O logC 级别 的 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 开开开阔阔阔视视视野野野 题题题目目目 分分分析析析 Wifi Planet 总总总结结结 感感感谢谢谢 二二二维维维欧欧欧几几几里里里得得得算算算法法法 分分分析析析 所以一个基于欧几里得算法的算法就成型了 每次用二次函 数计算上面的k值 之后进行变换 直到夹角超过 3 限于知识水平 这个算法的确切复杂度我不能给出 但是根 据实验结果 基本能在几步之内结束 应该是O logC 级别 的 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 题题题目目目 问问问题题题 TopCoder SRM 410 HARD writer bmerry 在整数格点的平面上有一个简单多边形 顶点坐标均为有理 数 问其内部有多少格点 题目保证不会有格点出现在 边界上 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 题题题目目目 问问问题题题 TopCoder SRM 410 HARD writer bmerry 在整数格点的平面上有一个简单多边形 顶点坐标均为有理 数 问其内部有多少格点 题目保证不会有格点出现在 边界上 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 分分分析析析 梯梯梯形形形剖剖剖分分分 三角剖分 梯形剖分 n 1 i 0 a di m b k 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 分分分析析析 梯梯梯形形形剖剖剖分分分 三角剖分 梯形剖分 n 1 i 0 a di m b k 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 分分分析析析 梯梯梯形形形剖剖剖分分分 三角剖分 梯形剖分 n 1 i 0 a di m b k 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 分分分析析析 梯梯梯形形形剖剖剖分分分 三角剖分 梯形剖分 n 1 i 0 a di m b k 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 分分分析析析 梯梯梯形形形剖剖剖分分分 三角剖分 梯形剖分 n 1 i 0 b ki b k 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 分分分析析析 梯梯梯形形形剖剖剖分分分 三角剖分 梯形剖分 n 1 i 0 a di m b k 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 n 1 i 0 a di m 约定 0 a m 否则直接可以把 a m 提到外面 0 d m 通过和上边式子一样的方法 可以保证这 一点 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 n 1 i 0 a di m 约定 0 a m 否则直接可以把 a m 提到外面 0 d m 通过和上边式子一样的方法 可以保证这 一点 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 n 1 i 0 a di m 约定 0 a m 否则直接可以把 a m 提到外面 0 d m 通过和上边式子一样的方法 可以保证这 一点 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 n 1 i 0 a di m 约定 0 a m 否则直接可以把 a m 提到外面 0 d m 通过和上边式子一样的方法 可以保证这 一点 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 n 1 i 0 a di m 约定 0 b 1 0 k 1 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 几几几何何何意意意义义义 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 几几几何何何意意意义义义 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 几几几何何何意意意义义义 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 几几几何何何意意意义义义 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 交交交换换换边边边 topY nowY 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 交交交换换换边边边 topY nowY l a dn m 条直线 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 交交交换换换边边边 topY nowY topY为a dn 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 交交交换换换边边边 topY nowY nowY为当前的直线高度 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 交交交换换换边边边 topY nowY 红点个数 topY nowY d 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 题题题目目目 分分分析析析 欧欧欧几几几里里里得得得 总总总结结结 感感感谢谢谢 Wifi Planet 欧欧欧几几几里里里得得得算算算法法法 交交交换换换边边边 n 1 i 0 a di m l 1 k 0 a dn mod m mk d 2 问题至此解决 欧欧欧几几几里里里得得得算算算法法法 的的的应应应用用用 金金金斌斌斌 总总总览览览 欧欧欧几几几里里里得得得算算算法法法 二二二维维维欧欧欧几几几里里里得得得 Wifi Planet 总总总结结结 感感感谢谢谢 总总总结结结 欧几里得虽然被大部分信息学竞赛选手所熟知 但是在实际 的运用中却很难被想到 实际上我们只要能挑出思维的定 势 从一些并不相关的等式把问题简单化 最后都是能到达 我们的目的的 本次论文主要从思想方面介绍了欧几里得算 法的