Homework 2

Problem 1

首先证明

这由

知

而 共有 种可能，这代表 的余数从 均恰好出现一次，即存在唯一的 满足

Problem 2

首先，我们关注 的正负性：从底部开始向上分析

可见：若一个扩展欧几里得算法向上算到第三步，即第一次 异号后，此时 ，下一次由于 ，必有新的

而下一次又进一步变为

故保持 异号，且每次向上迭代都各自变一次号的情况

下面开始证明：

1. 对于 base case，这里特殊判别前三步的情况，第一步 ，在题目中不考虑，第二步即 的情况，则

满足，第三步中

故也成立

2. 对于第三步以上的部分，若假设对于 与 成立，即

则由前面的讨论知 异号，所以

故假设对 和 也成立

综上知证毕

对于 ，可计算

Ex(11, 25) -> Ex(25, 11) -> Ex(11, 3) -> Ex(3, 2) -> Ex(2, 1) -> Ex(1, 0) = (1, 0, 1) => (0, 1, 1) => (1, -1, 1) => (-1, 4, 1) => (4, -9, 1) => (-9, 4, 1)

故答案为

Problem 3

(i)

(ii)

(i) 中算法的复杂度就是扩展欧几里得算法的复杂度 ，得到的 满足

故

直接输出即可，因此复杂度为

当公约数较小的时候比较高效

伪代码为

(iii)

从 (ii) 的分析可见，二者的大小相同均为

Problem 4

(a)

运行时间为

(b)

若 ，则 ，则

即证

(c)

综合 (a)，(b)，即有

不经优化的这一算法复杂度有

1. 循环 次
2. 二分至多遍历 级别次
3. 每次二分内部计算 需要 次运算

故整体时间复杂度为

通过对幂运算做优化（快速幂）可以变为

Problem 5

对于所有的 ，我们知道

由容斥定理，设

不满足的总数为

则

故答案即