搜索
模线性方程的应用——用数论方法解决整数问题引言数论是数学的一支它的研究对象是整数的性质模线性方程表现形式：ax≡c(modb)或ax+by=c定理：模线性方程有解的充要条件是gcd(a,b)|c若模线性方程有解，从模的意义上讲有且只有一解。实现：Extended-Euclid算法例题——ball小球从棋盘左侧或下侧的某格出发，斜向上运动碰到棋盘的边规则反弹，碰到角落沿原路返回问小球第一次回到起点时，有几个格子滚过奇数次？转化分析设转化后的棋盘边长分别为L、H，则小球将会作周期为2Lcm(L,H)的周期运动。小球的运动有两种：撞到角上，沿原线路返回，以和出发相反的方向回到起点。没有撞到角上，以和出发相同的方向回到起点。情况1：撞到角上水平方向运动距离：qL竖直方向运动距离：pH-a条件：gcd(L,H)|a。qL=pH-a即pH-qL=a结论：只有两个点经过了奇数次。情况2：没有撞到角上问题：小球滚过一个点至多几次？推论2：小球不可能以同一方向滚过一个点两次推论3：小球不可能以相反方向滚过一个点两次结论：滚过四边上的点至多一次，滚过中间的点至多两次。推论1：小球经过的总路程为2Lcm(L,H)。情况2：没有撞到角上小球经过奇数次的点的个数=2Lcm(L,H)-小球经过偶数次的点的个数*2情况2：没有撞到角上经过一个点两次时子情况1：水平方向相反，竖直方向相同；子情况2：水平方向相同，竖直方向相反。水平方向相反，竖直方向相同假设这个点在水平方向的投影为x水平向右运动距离：2k1L+x0≤k1H/g水平向左运动距离：2k2L-x0k2≤H/g水平距离差：(2k1L+x)-(2k2L-x)(2k1L+x)-(2k2L-x)≡0(mod2H)水平方向相反，竖直方向相同(2k1L+x)-(2k2L-x)≡0(mod2H)(k1-k2)L+x≡0(modH)0≤k1H/g0k2≤H/g条件：gcd(L,H)|x结论：x共有L/gcd(L,H)-1个对于任意的x(k1-k2)L+x≡0(modH)0≤k1H/g0k2≤H/g(k1-k2)≡V(modH/g)只有一解。无论V为何值，方程有且仅有H/g组解结论：水平方向相反，竖直方向相同的情况下共有(L/g-1)*H/g组解水平方向相同，竖直方向相反类似的可以得到：水平方向相同，竖直方向相反的情况下共有(H/g-1)*L/g组解结论所以问题的解为：当g|a，答案为2；否则为2LH/g-2((L/g-1)*H/g+(H/g-1)*L/g)。小结从反面思考问题模线性方程的解的判定定理分类讨论的思想简化复杂的问题总结数论问题的特点和整数有关数据量大，无法用一般方法解决数论问题解决方法建立数论模型对定理的熟练掌握各种思维方法