poj1061 青蛙的约会 扩展欧几里德的应用

这个题解得改一下,开始接触数论,这道题目一开始是看了别人的思路做的,后来我又继续以这种方法去做题,发现很困难,学长告诉我先看书,把各种词的定义看懂了,再好好学习,我做了几道朴素的欧几里德,尽管是小学生一样的题目我还是坚持做了几道,然后 看了中国余数定理 跟 中国剩余定理 还有扩展欧几里德的定义以及介绍,这次 这个题目是我自己思考出来的,这个题解是写给自己看的  同时向大家共享,学长说 做数论 要不时的回头 看看以前的题目 做做过了的题目,所以留个纪念

这道题目关节解决句是:

可以这样思考:
对于a' = b, b' = a % b 而言,我们求得 x, y使得 a'x + b'y = Gcd(a', b')
由于b' = a % b = a - a / b * b (注:这里的/是
程序设计语言中的
除法)
那么可以得到:
a'x + b'y = Gcd(a', b') ===>
bx + (a - a / b * b)y = Gcd(a', b') = Gcd(a, b) ===>
ay +b(x - a / b*y) = Gcd(a, b)
因此对于a和b而言,他们的相对应的p,q分别是 y和(x-a/b*y)
使用扩展欧几里德算法解决不定方程的办法
对于不定整数方程pa+qb=c,若 c mod Gcd(a, b)=0,则该方程存在整数解,否则不存在整数解。
上面已经列出找一个
整数解的方法,在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后,
/*p * a+q * b = Gcd(a, b)的其他整数解满足:
p = p0 + a/Gcd(a, b) * t
q = q0 - b/Gcd(a, b) * t(其中t为任意
整数)
至于pa+qb=c的整数解,只需将p * a+q * b = Gcd(a, b)的每个解乘上 c/Gcd(a, b) 即可
在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后,应该是
得到p * a+q * b = c的一组解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b)),p * a+q * b = c的其他整数解满足:
p = p1 + b/Gcd(a, b) * t
q = q1 - a/Gcd(a, b) * t(其中t为任意
整数)
p 、q就是p * a+q * b = c的所有
整数解。

首先上述是扩展欧几里德的一些 性质,对解本题很有作用,设走了t步,一开始我们列出方程

(x+mt-y-nt)%L==0;

再次化简方程,因为有应用欧几里德来解释方程肯定需要两个变量

(m-n)t+x-y=L*p(这里的p是一个整数,因为绕地球是一个圈嘛,所以有可能绕了很多圈)

移项:

(n-m)t+Lp=x-y;

此时若n==m  或者 (x-y)%gcd(n-m,L)!=0  则方程无解,也就是说青蛙遇不到,这个上述扩展欧几里德性质中都有

接下来解方程

令 (n-m)t+Lp=gcd(n-m,L);

因为t,p的解是不止一组的,我们设其中一组为t0,p0;

直接用扩展欧几里德模版获得t0的值

那么t=t0*(x-y)/gcd(n-m,L)//这个也是扩展欧几里德性质之一

得到的t其实就是正确答案,可是 我们本题一开始的思想 就是在一个 无限循环的 一维坐标上进行的,比如本题案例 ,到目前这一步跑出来的答案是t=-1,实际上我们大家都知道 其实相当于t=4,因为t有无数组解,-1,4只是其中两组,实际上t=-1+L*k(k是一个正整数),最小正解就是k=1的时候

所以最后t=(t%MOD+MOD)%MOD;//MOD=L/gcd(n-m,L);

下面给出代码青蛙的约会

上一篇:SQL内联多个表


下一篇:设置Session的超时时间