1、第五章 数论中的程序设计沈云付上海大学计算机工程与科学学院本章主要内容5.1 从跳兽问题谈起5.2 最大公因数与最小公倍数5.3 求整系数一次不定方程 ax+by=c的解5.4 求解模线性方程5.5 求模 m的逆元素算法5.6 模线性方程组与中国剩余定理5.7 模取幂运算与素数测试5.8 二次剩余与 Pell方程5.9 实例研究1234567895.1 从跳兽问题谈起例 1：跳兽问题：问题描述：一只神奇的野兽，它跳一步的长度是某个部落的人们所走步长的 m倍，它只在一条长度为 n步长的道路上来回不停地跳动。当它接近道路的一个端点，但余下距离又不足它的一步时，它会先跳到端点，再折回，其折回的距离是
2、刚才一跳未跳完部分的长度。要求捕捉这只野兽，方法就是把捕捉工具放到这只野兽面前，距离是人一步长的地方。问能否捕捉到这只野兽？请你帮助 酋 长 解决这个问题。图示 1输入：输入有若干行。每行上有两个整数 n、 m， 之间用一个空格隔开，其中 n表示道路的长度（步数）， m表示野兽跳的步长，（ n50000， m2000）。 假定野兽在道路的一端，捕捉工具放在野兽前一步长的地方。输出：对输入文件每一行的两个整数 n、 m， 确定能不能捕捉到这只野兽？若可以捕捉到，则输出 “ possible” ，否则输出 “ impossible” 。 输入与输出输入样例：20 312345 6输出样例：poss
3、ibleImpossible分析 野兽跳的情况如下： m， 2m， 3m， ， (k-1)m， 有折回： 第 k步 时 恰好 到达 终 点就回跳 ,距离是多少？ 结论： 野 兽 跳到位置是 n、 m的 线 性 组 合： nx+my 进一步：要跳到 1的位置，需有 x， y使 nx+my=1 但 满足 nx+my=1 未必保证一定跳到离洞口 1步距离，为什么？ 经分析，跳到洞口 1的充分和必要的条件是 GCD(2n,m)=1来回跳跃环形示意图 5.2 最大公因数与最小公倍数1 公约数和最大公约数的概念2 最大公约数的一种求法 分解因子3 最大公约数性质与欧几里德转辗相除法4 欧几里德转辗相除法5 欧几里德算法实现实例 求最大公因数问题描述：从输入文件中读取一组数据，求最大公因数。输入：输入有若干行。每一行上有两个整数 x， y， 是一组测试数据，他们之间用一个空格隔开。输出：对每一组测试数据，每行输出这两个整数的最大公因数。如无最大公因数，则标明 “ no GCD” 。输出样例：(6,11)=1(0,0) no GCD(5,0)=5输入样例： 6 110 05 0
