icontofig | 发布于 2019-06-04 00:08:00 | 阅读量 399 | 数论 同余线性方程
发布于 2019-06-04 00:08:00 | 数论 同余线性方程
POJ 青蛙的约会 扩展欧几里得解同余线性方程
题解青蛙的世界真是简单啊,而人类就不一样了QAQ 扯远了扯远了…… 对这个题目进行比较小的数学建模,我们可以得到这样一个式子 然后我们移一下项,可以得到  我们要求解的就是t的最小值。 上式可以转化以下一元二次不定方程:  然后我们都清楚一元二次不定方程的解法无非就是扩展欧几里得…… 其中如果gcd((m-n),l)不能整除(y-x)的话,此方程则是无解的,直接输出Impossible。 否则的话,就利用扩展欧几里得去计算t。 先对两边式子的系数同时除以gcd((m-n),l),利用扩展欧几里得算法解出a*t’ + b*p‘ = 1的解中的t’,然后再乘(y-x)/g
继续阅读