模线性方程解题报告

1、NOI2002 Day2 Problem1荒岛野人解题市中学二二年十一月问题分析：看过试题容易想到，在所以人中选出最大起始位置 max，从 max 起逐个检测是否满足条件。但由于洞的个数最大为 106，所以单纯摸拟肯定要超时（只能过 4 个点），必须进行优化。进一步分析，这是一个追击问题，对于某两个野人，如果他们速度相同则满足条件，若速度不同则要看在两人有生之年，速度快的野人能否追到速度慢的野人或超过其整数圈。设两野人为 w1,w2;rabw1,w2.p 为速度差的绝对值;rabw1,w2.c 为速度慢的野人起始位置速度快的起始位置；rabw1,w2.L 为较短的方程 xw1,w2*rabw1

2、,w2.prabw1,w2.c(mod m)(1=w1,w2=n, xw1,w2=rabw1,w2.L)永不成立.以下简写为 xpc(mod m)值，则洞的个数 m 需要满足的条件为：队友在不了的做法：余方程的情况下，是一种好方法（可过 9 个点）。将同余方程 xpc(mod m)改写为不定方程 xp=ym+c，由于 1=x=106 而 1=p=100,所以(ym+c) mod p 最多只有 100 种可能的取值，从 1100 依次搜索 y 若值为 0 且 xL,则 m 不符合要求，若值出现重复，则此二人不会碰到，继续搜索直至m 对所有方程均成立。标答：余方程。（参见黑书 P63）对于 xpc

3、(mod m) 1应用扩展求出 xp+ym=法（辗转相除）（参见后面的辅助说明）(p,m)(最大公约数)(p,m)即 xp=d+ym xpd(mod m)mod d0 则方程无解（参见附录定理 4），二人 mod d=0 则方程有 d 个解（参见附录定理 6），设 d=2. 若 c若 c不会相遇。这些解为 x0=x*(c div d) mod m=x*(c/d) mod m，（参见附录定理 5） xi=(x0+i*(m/d) mod m=(x*(c/d)+i*(m/d) mod m (i=0.d-1)若 xiL 方程无解，否则 m 不合条件继续检测更大的 m。优化：只需求出 xmin 并判断其

4、与 L 的关系，根据同余知识可知 xmin=x*(c/d) mod标程解了两次同余方程，是没有必要的，重复了。另外，此时求 xi 可简化为 xi=xmin+i*(m/d)(i=0.d-1).(m/d)辅助说明：以下给出中提到一些数学知识。扩展（辗转相除）函数：function extended_euclid(a,b:long;var x,y:long):long;var t:long beginif b=0then begin;extended_euclid:=a;x:=1;y:=0 endelse beginextended_euclid:=extend_euclid(b,a mod b,x

5、,y); t:=x;x:=y;y:=t-(a div b)*yend;end;此函数满足：ax+by=extended_euclid=(a,b)有关一次同余方程的定理归纳（请先阅读同余的一些基本性质）。对于同余式：axb(mod m)的一个解并不是一个数，而是包含对模 m 同余的一组数（此题中只求最小的）模 m 的一个剩余类。即，凡对模 m 同余的数，算作一个解，只有对模 m互不同余的数，才是不同的解。剩余类：模m 同余的整数的集合。完全剩余系（完系）：从模 m 的每一个剩余类中任意挑出一个整数，则这 n 个整数就称为模m 的一个完全剩余系。定理 1 若(a,m)=1,则必存在 a*,使 aa

6、*b(mod m)。证明：因为(a,m)=1,所以存在 a*,y,使 aa*+my=1.由此 aa*1(mod m), a*称为 a 的数论倒数。只有与模互素的数才有数论倒数，并且一个数的数论倒数在同余意义下是唯一的。定理 2 若 ab(mod n),m|n,则 ab(mod m)。证明：因为 ab(mod n),所以 n|a-b,又因为 m|n,所以 m|a-b,故 ab(mod m)。定理 3 若(a,m)=1,则同余式 axb(mod m)有且只有一解.证明：设 1,2,3是模 m 的一个完全剩余系，(a,m)=1,所以 a,2a,ma 也是模 m 的一个完全剩余系（可用反证明），其中有

7、一数，设为 ak，满足 akb(mod m),则 xk(mod m)就是 axb(mod m)的唯一解。定理 4 设(a,m)=d1,同余式 axb(mod m)有解的通分必要条件是 d|b.证明：必要性(“=”):设同余式 axb(mod m)有解，则由 d|a,d|m,可推知 d|b.充分性(“1,d|b,则同余式 axb(mod m)有且只有 d 个解.它们是 r+km(arb(mod m)(k=0.d-1)，且数值最小的非负解是 r。分析：首先证明同余式 axb(mod m)的解为 r+km(k 为整数)其次构造 d 个数，都适合同余式 axb(mod m)然后证明除去这 d 个解外，

8、没有其它的解.最后证明 r 是数值最小的非负解。证明：首先证明同余式 axb(mod m)的解r+km(k 为整数)必要性（=）设 a=da,b=db,m=dm,此时(a,b,m)1，可知同余式 axb(mod m)有且只有一解（定理 3），设为 r若 r满足 axb(mod m)则必满足 arb(mod m),所以 rr(mod m)充分性（=）a(r+km)=dar+dakm=ard+ak(dm)(k=1.d-1),因为 dm=m,所以 arb(mod m)(参见定理 2)。于是 ard+ak(dm) bd+akmbdb(mod m).即 a(r+km) b(mod m).所以 axb(m

9、od m)的解为 r+km（k 为整数）。则 0rr+mr+2m r+(d-1)mm+(d-1)m=dm=m,满足 axb(mod m)。其次证明中 d 个数对模 m 互不同余（即有 d 个解）。因为 0.d-1 是模 d 的最小非负完系(完全剩余系)， 所以中 d 个数是模d 的非负完系。若有 r+kmr+km(mod m)(kk),则可推得 k=k（mod d），与所设不符。因而中 d 个数恰是同余式 axb(mod m)的 d 个不同余的解。然后证明不再有其它解（即只有 d 个解）反证法：假设存在第 d+1 个解 r+km，且 k 为整数则 r+km不同余 r+km(mod m)(k=0

10、.d-1)则 k 不同余 k(mod d)(k=0.d-1),与 k 为整数所以原命题成立。最后证明r 是数值最小的非负解。反证法：假设存在解 0r+kmrm(k 为整数且不为 0),0rm-1则 k(m-r)/m1 且-1max end; close(input); for i:=1 to n-1for j:=i+1 tothen max:=ri.c;do beginn do begin确定每组追击问题的参数，即构造同余方程if ri.prj.pthen begin rabi,j.p:=ri.p-rj.p;rabi,j.c:=rj.c-ri.c; endelse begin rabi,j.p

11、:=rj.p-ri.p;rabi,j.c:=ri.c-rj.c; end;if ri.lrj.lthen rabi,j.l:=rj.lelse rabi,j.l:=ri.l;end; end;end;procedure out(x:long输出可行解 begin);assign(output,savage.out);rewrite(output);wrin(output,x);close(output); haltend;procedure solve;var i,x0,a,b,m,d,tx,x,y:long;w1,w2: flag:beginfor i:=maxeger;to 1000000do beginflag:=true;for w1:=1 to n-1 do flag:=true;for w2:=w1+1 to nbegindo beginif rabw1,w2.p0 then begin d:=extended_euclid(rabw1,w2.p,i,x,y);tx:=x;确定是否有解if (rabw1,w2.c mod d=0) then begin b:=rabw1,w2.c div d;m:=i div d;求出一解 x0:=x*b;求非负最小解while (