1、ACM中的数论北京大学 ACM队李晔晨 模，同余 最大公约数和最小公倍数 素数，互素 正整数的素因数分解本讲要点 扩展 gcd与裴蜀定理 模线性方程 模线性方程组 中国剩余定理 高斯消元法 筛法线性求素数 欧拉函数扩展 gcd与裴蜀定理 最大公约数： d = gcd(a,b) 裴蜀定理：存在 u,v使得a*u + b*v = d 裴蜀定理特例：若 a,b互质， gcd(a,b) = 1则存在 u,v 使得a*u + b*v = 1 设 a = pd, b = qd, 则 p,q互质（为什么？）裴蜀定理 pdu + qdv = d - pu + qv = 1 转化为特例裴蜀定理的 证明 直接构造
2、出 u,v au + bv = d (a-b)u + b(u+v) = d 令 a = a%b, 令 t使得 a = b*t + a t = a/b (a-tb)u + b(tu + v) = d au + b(tu+v) = d 令 v = tu+v, 得到 au + bv = d 令 v = tu+v, 得到 au + bv = d v = v tu 若知道 (u, v)则可知道 (u,v)int gcd(int a, int b)return b=0?a:gcd(b,a%b);int ex_gcd(int a,int b, int Return a;int d = ex_gcd(b, a
3、%b, v, u);v = v - a/b *u;return d;注意 1这里反转注意 2这里容易溢出扩展 gcd算法模线性方程 ax = d (mod b) abd 已知求 x 转化为 ax + by = d 用扩展 gcd求 x,y 注意 2容易溢出 在求 x,y的中间步对其 mod b处理中国剩余定理 设 n组数 (ai, bi), 其中 bi两两互素 求 x使得 x = a1 mod b1x = a2 mod b2.x = an mod bn中国剩余定理 令 B = b1*b2*b3*bn 令 ci = B/bi = b1*b2*.*b(i-1)*b(i+1).*bn 显然有 ci 与 bi互素，从而存在 mi满足mi*ci = bi (mod b) x = a1b1m1 + a2b2m2 + +anbnmn 为什么这个 x是解？ 联想：拉格朗日插值公式！中国剩余定理 设 n组数 (ai, bi), 其中 bi两两互素 如果 bi不是两两互素呢？ 另一个角度看此问题 x = a1( mod b1) x = a2( mod b2) -x + u*b1 = a1, x - v*b2 = a2 - u*b1 + v*b2 = (a1-a2) 化为裴蜀定理的一般情况，有解当且仅当 gcd(b1, b2) | (a1-a2)
