数论中的程序设计 沈云付.pptVIP

第五章 数论中的程序设计 沈云付 yfshen@staff.shu.edu.cn 本章主要内容 5.1 从跳兽问题谈起 5.2 最大公因数与最小公倍数 5.3 求整系数一次不定方程ax+by=c的解 5.4 求解模线性方程 5.5 求模m的逆元素算法 5.6 模线性方程组与中国剩余定理 5.7 模取幂运算与素数测试 5.8 二次剩余与Pell方程 5.9 实例研究 5.1 从跳兽问题谈起 例1：跳兽问题： 问题描述： 一只神奇的野兽，它跳一步的长度是某个部落的人们所走步长的m倍，它只在一条长度为n步长的道路上来回不停地跳动。当它接近道路的一个端点，但余下距离又不足它的一步时，它会先跳到端点，再折回，其折回的距离是刚才一跳未跳完部分的长度。要求捕捉这只野兽，方法就是把捕捉工具放到这只野兽面前，距离是人一步长的地方。问能否捕捉到这只野兽？请你帮助酋长解决这个问题。 输入与输出 输入样例： 20 3 12345 6 输出样例： possible Impossible 分析 野兽跳的情况如下：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”。 5.2.1 公因数和最大公因数的概念 公因数：如果d是a的因数并且也是b的因数，则d是a与b的公因数 例：30的正因数： 1，2，3，5，6，10，15、30； 24的正因数：1，2，3，4，6，12，24； 24与30的正公因数有：1、2、3、6。 1是任意两个整数的公因数； 最大公因数：两个不同时为0的整数a与b的最大公因数是其值为最大的公因数，记作gcd(a, b)。 gcd(24, 30)＝6。 最大公约数的一种求法—分解因子 因为gcd(a，b)＝gcd(|a|，|b|)，所以可考虑非负整数的情况。 通过求因数，可求a和b的素数因子分解： a= ，b= 于是整数a和b的最大公因数为： gcd(a，b)＝ 最大公因数性质 性质： （1）gcd(a，b)＝gcd(? a，? b) （2）gcd(a，b)＝gcd(a + kb， b)，k为任何整数 （3）gcd(a，b)＝gcd(b，a mod b) （4）如a是非零整数，那么gcd(a，0)＝|a| 5.2.2 最小公倍数 公倍数：如果m是a的倍数并且也是b的倍数，那么称m是a与b的公倍数。 最小公倍数：两个非零整数a与b的最小公倍数是a与b的公倍数中数值最小正的数，记作lcm(a，b)（或简写为[a，b]）。 lcm(a，b)＝lcm(|a|，|b|) 通过a和b的标准分解，可以求出整数a和b的最小公倍数： lcm(a，b)= 5.2.3 欧儿里德算法 给定任意两个正整数a和b 求最大公因数的递归程序 用欧几里德转辗相除法构造一个求最大公因数的递归程序。 输入：非负整数a、b 返回：a和b的最大公因数 long gcd(long a, long b){ long m; if ((b==0)(a==0)) //表示无最大公因数 return -1; if (b==0) return a; else m=gcd(b, a%b); return m; } 求最大公因数的无递归程序 int gcd(int a,int b) { int c; if(a ==0) return b; while(b!=0) c=b,b=a%b,a=c; return a; } 5.3 利用欧几里德算法求整系数一次不定方程ax+by=c的解 算法思想： 利用求a,b的最大公因数的转辗相除过程，进行多次逆推，使最大公因数的表示式最终表示为a与b的线性组合ax+by (x与y可能为0或负数) 。 此时，d＝gcd(a,b) 做