线性同余方程解法：Euler函数与扩展欧几里得算法

"线性同余方程是数学和计算机科学中的一个重要概念，特别是在数论和密码学中有着广泛的应用。在ACM竞赛中，掌握解这类方程的方法是至关重要的。线性同余方程通常表示为 `ax ≡ b (mod n)`，其中a, b, n为整数，模n的含义是结果对n取模后的余数。解决这类方程的方法主要有两种。 方法一是利用欧拉函数。欧拉函数φ(n)表示小于等于n且与n互质的正整数的个数。如果a和n互质，那么存在一个整数k使得a^φ(n) ≡ 1 (mod n)。为了求解 `ax ≡ b (mod n)`，我们可以将b表示为二进制，然后通过计算a的幂次（如a, a^2, a^4等）与b对应的二进制位相乘，最后对n取模，得到解。 方法二是扩展的欧几里得算法。扩展的欧几里得算法不仅可以找到两个整数的最大公约数，还可以找到满足ax - ny = d的解（其中d是a和n的最大公约数）。当d|b（即d整除b）时，我们可以通过这个算法找到线性同余方程的解。解可能不是唯一的，因为所有x相差n/d的整数倍也是解。 在ACM竞赛中，掌握这些算法和数据结构对于解决复杂问题至关重要。例如，线性同余方程的解法可能用于编码和解码问题、数论问题以及其他需要高效计算的场景。ACM/ICPC（国际大学生程序设计竞赛）是由美国计算机学会（ACM）主办的一项全球性比赛，旨在提升大学生的编程技能和解决问题的能力。参赛者需要在限定的时间内，使用C/C++或Java编写程序解决一系列题目，题目涵盖各种算法和数据结构，包括线性同余方程的求解。比赛通常以团队形式进行，通过解题数量和用时来评判胜负。中国的许多顶级大学，如清华大学和上海交通大学，都有积极参与ACM/ICPC的传统，并取得了显著的成绩。" 这段摘要详细介绍了线性同余方程的两种解法，以及它们在ACM竞赛中的应用背景。同时，它也概述了ACM/ICPC竞赛的起源、目的和规则，强调了解决这类问题对于参赛者的重要性。