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

2024-01-31 18:34:10

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

这道题目关节解决句是：

可以这样思考:

对于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);

下面给出代码青蛙的约会

码农公寓

相关文章