如何准备欧几里得数学竞赛
定义：形如 ax\equiv c\pmod b 是同余方程。
由第四章开头提到的同余的等价定义，上面的同余方程等价于关于 x,y的不定方程 ax+by=c 。 y 这个自由度表达了同余关系。
上面这个方程是平凡的，直接用扩展欧几里得算法求出特解，然后再用上面的通解公式表示一下就可以了。
我们有一个结论：对于一个同余方程，若有解，则恰有 \gcd(a,b) 个模 b 不同余的解。
为了确定有多少不同余的解，我们先来找两个解 x_1=x_0+k_1\frac{b}{g},x_2=x_0+k_2\frac{b}{g} 。
若有 x_0+k_1\frac{b}{g}\equiv x_0+k_2\frac{b}{g}\pmod b ，同减 x_0 ，有 k_1\frac{b}{g}\equiv k_2\frac{b}{g}\pmod b 。
显然， \gcd(b,\frac{b}{g})=\frac{b}{g} 。由第四章讲的同余的除法性质，同时除以 \frac{b}{g} 有 k_1\equiv k_2\pmod {b/\frac{b}{g}} ，也就是 k_1\equiv k_2\pmod g 。
所以说反过来，只要 k_1,k_2 模 g 不同余，则方程的两个解就模 b 不同余。
那我们让这个 k 取遍 g 的完全剩余系，就可以得到 g 个模 b 不同余的解了。
刚好三千字。
对于那些有初中基础的备考生来说，前面几题拿满分应该不是大问题。随着难度的递增，会涉及到一些统计概率和竞赛技巧方面的知识，例如一小部分的基础数论。还有最最最难点就是偏计算机里的recurrence和几何与代数的结合（记得去年的最后一题就是考了三个圆的相切）。
建议同学们先去官网看看真题，大致浏览一遍考点范围和自己不太掌握的知识点大块，再针对难点专门训练。可以把前6题和后4题进行区分，因为后面的难度提升比较大。专门练习后面的难点，即便做不出全部，也可以尽可能完成1-2小问，因为至少有步骤分嘛。
对于做填空题而言，也建议把解题过程写在卷子边上，这样考官也看得见你的思路，或许良心给分呢。另外，英文的官方书写在欧赛中也很重要。我们要力求解题步骤书写规范。一定要用字面语言完全表达想说明的含义，如果模糊不清书写不规范，即使答案错了也会被扣分的。
1. 历年真题：
官网有历年真题可以下载，并附有详细解答，非常重要的备考资料！大家可以在接触竞赛前先翻翻真题，了解大概的考试形式及内容，再找出自己的薄弱点针对性的复习。有需要的同学们可以滑到文末查看真题领取方式哦！
2. Euclid eWorkshop：
备战Euclid有一份官方讲义也很好用，分了六个章节进行讲解，里面列出了需要掌握的知识点以及配套的练习。大家可以很方便的根据自己的薄弱点找到对应的topic进行学习，官网给出的题目和讲解都对备考欧几里得数学竞赛很重要。讲义资料的领取方式见文末。
但是里面的知识点不全，课后练习的题目比较老，还是建议直接做近几年真题。
我建议大家重点刷最近5年的真题，一开始先从最早的年份做起，可以先不计时，看看自己大概的水平，再通过集中训练提升弱项。如果真的没有题目做了的话其实可以尝试做美国AMC中15题之后的题目。虽然考点内容不完全一样，但是针对欧赛的后两题的解题思路，其实是大同小异的。练习灵活的解题思维在欧赛中很重要。
欧几里得攻略
扩展欧几里得算法是一种求解线性同余方程特解的算法。
我们考虑传统欧几里得算法迭代的过程： \gcd(a,b)\to\gcd(b,a\bmod b) 。由线性组合的推论，存在 x_1,y_1,x_2,y_2 使得 \gcd(a,b)=ax_1+by_1 ， \gcd(b,a\bmod b)=bx_2+(a\bmod b)y_2 。
由于 \gcd(a,b)=\gcd(b,a\bmod b) ，所以我们得到恒等式：
\displaystyle ax_1+by_1=bx_2+(a\bmod b)y_2 \\ 由于 a\bmod b=a-b\lfloor\frac{a}{b}\rfloor ，所以说上式可以变形为：
\displaystyle ax_1+by_1=bx_2+(a-b\lfloor\frac{a}{b}\rfloor)y_2 \\ 稍作整理，得到：
\displaystyle ax_1+by_1=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2) \\ 于是我们得到： x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2 。
这告诉我们，欧几里得算法只要在某一层得到了解，这个解是可以传递回去得到原方程的解的。
考虑传统欧几里得算法的边界是 b=0 ，此时 \gcd(a,b)=a ，因此关于 ax+by=\gcd(a,b) 在此时有一组显然的特解： x=1,y=0 。我们在回溯的时候用上面推导得到的式子拿过来一层层迭代到原始状态就行了。
Talk is cheap.
我们发现这个算法本质上还是在运行欧几里得算法，只不过“顺便”记录了一下 x 和 y ，因此复杂度还是 O(\log n) 。
欧几里得攻略
关于 x,y 的不定方程 ax+by=c 有解当且仅当 \gcd(a,b) 是 c 的一个因子。
证明：我们记 g=\gcd(a,b)
由引理，对于每一个 ax+by ，都满足 g\mid c 。
为了证明充要性，只需要反过来证明，对于c=gk （ k 是任给的）， gk 可以被一组给定的 x,y 表示为 ax+by 的形式。
由上面关于线性组合的推论， \exists r,s\in\mathbb{Z}\to g=ra+sb 。同乘 k ，有 gk=rka+skb ，取 x=rk,y=sk 即为一组解。
这就证明了Bézout定理。
