讲义文稿教程1

1、从例题中看数学的重要性信息科学技术学院林晓辉00348272目的介绍一道题，引发大家的一点感想介绍一点数学知识（可能是大家都知道的）下面开始抛砖引玉了青蛙的约会 两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否

2、能够碰面，会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。 POJ 1061输入只包括一行5个整数x，y，m，n，L，其中xy 2000000000，0 m、n 2000000000，0 L 0)问题转化为：求满足 A*t+Lp=B 的最小 t (t0)即求 一次同余方程 A*t = B (mod L) 的最

3、小正整数解 至此，我们已经将问题完全转化成一个数学问题了，但问题是.How to Solve it ?算法一：穷举 A* t = B (mod L)注意到：上面方程的解是模L同余的所以可以试一下穷举 搜索被称为“通用解题法”，在算法中占有重要地位 搜索算法也是有不少技术含量的代码（略）显然上面的算法是会超时的算法二反思抽象过程：根据题意，得到二元一次不定方程，然后得到一次同余方程，然后试图解该方程得到答案。能不能直接解不定方程其实这时就靠数学功底了。定理：设a,b为不全为零的整数，那么 存在x,y Z,使得 a*x+b*y=gcd(a,b)证明思路：考虑集合S=a*x+b*y | x,y Z(

4、1) m,n S = m+n ,m-n S(2) 设S中最小的正整数为d，则 x S d | x由上面的陈述，立即可以得到判断青蛙是否能相遇的条件BTW: 是数论中的一条基本的公式。怎样解一次不定方程设二元一次不定方程ax+by=c有解，X,Y时它的一组解，则其所有解为 x=X+b/(a,b)*t y=Y+a/(a,b)*t t Z证明那么现在的问题就是求出方程 (n-m)*t+Lp=x-y 的任意一组解 T,PG=L/(n-m,L)则 (T%G+G)%G就是所求的答案 注意C+中的%运算并不是数学上的求模（-1）%2=-1假设：你不知道扩展的Euclid 算法你应该已经掌握 Euclid 算

5、法int gcd(int m,int n) / Euclid int r=(m%n+n)%n; while(r) m=n;n=r;r=m%n; return n; Euclid算法是怎么来的？定理：设u0,u1是给定的的两个整数，u1!=0, 则我们可以得到下面k+1个等式： u0=q0*u1+u2 u1=q1*u2+u3 u(k-1)=q(k-1)*u(k)+u(k+1) U(k)=q(k)*u(k+1) 我们要求的gcd 就是 u(k+1)由上面的定理可以方便得到Euclid算法能不能用类似的方法求得 x,y 使得 a*x+b*y=gcd(a,b) ?将前面所述定理变形如下 u(1)= 0

6、*u(0)+1*u(1)u(2)=u(0)-q(0)*u(1)u(3)= u(1)-q(1)*u(2) u(k+1)= u(k-1)-q(k-1)*u(k)设 u(j)=x(j)*u(0)+y(j)*u(1) u(j+1)= u(j-1)-q(j-1)*u(j) = u(j-1)-q(j-1)*(x(j)*u(0)+y(j)*u(1) =u(j-1)-q(j-1)*x(j)*u(0)-q(j-1)*y(j)*u(1) =(x(j-1)-q(j-1)*x(j) )*u(0) + (y(j-1)-q(j-1)*y(j) )*u(1)由此求出x(j+1),y(j+1) x(k+1),y(k+1)即为

7、所求x,y综上所述typedef unsigned long long int64 / g+int64 exgcd(int64 m,int64 & x,int64 n,int64 & y) / Extend Euclid int64 x1,y1,x0,y0;x0=1;y0=0;x1=0;y1=1; int64 r=(m%n+n)%n;int64 q=(m-r)/n;x=0;y=1;while(r) x=x0-q*x1;y=y0-q*y1; x0=x1;y0=y1; x1=x;y1=y; m=n;n=r;r=m%n; q=(m-r)/n;return n;int main()int64 r,t;int64 x,y,m,n,l;cinxymnl;int64 ar,br;int64 M=exgcd(n-m,ar,l,br);if(x-y)%M|m=n)coutImpossibleendl;else int64 s=l/M; ar=ar*(x-y)/M); ar=(ar%s+s)%s; coutarendl;return 0;写在后面的话数学能力 （