POJ 青蛙的约会 扩展欧几里得解同余线性方程

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

题解

青蛙的世界真是简单啊,而人类就不一样了QAQ

扯远了扯远了……

对这个题目进行比较小的数学建模,我们可以得到这样一个式子

然后我们移一下项,可以得到 

我们要求解的就是t的最小值。

上式可以转化以下一元二次不定方程: 

然后我们都清楚一元二次不定方程的解法无非就是扩展欧几里得……

其中如果gcd((m-n),l)不能整除(y-x)的话,此方程则是无解的,直接输出Impossible。

否则的话,就利用扩展欧几里得去计算t。

先对两边式子的系数同时除以gcd((m-n),l),利用扩展欧几里得算法解出a*t’ + b*p‘ = 1的解中的t’,然后再乘(y-x)/gcd(m-n,l)转化为需要的t。

此时不一定能够保证t为最小非负值。只需要t 对 (l/gcd((m-n,l)))取膜(如果t<0则取膜后再加膜数),即得到最终结果。

扩展欧几里得算法的讲解与证明将在之后的一篇博客中给出。

代码

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;
ll a, b, n, m, l;
void gcd(ll a, ll b, ll &d, ll &x, ll &y){
    if(b == 0){
    	x = 1;
    	y = 0;
    	d = a;
    	return;
    }
    gcd(b, a % b, d, x, y);
    ll tp = x;
    x = y;
    y = tp - (a / b) * y;
    return;
}
ll ans,ans2,g;
int main(){
    while ((cin >> a >> b >> m >> n >> l)){
        ll sp = m - n;
        ll d = b - a;
        if(sp < 0){
            sp = -sp;
            d = -d;
        }
    	if(sp == 0 && d != 0){
    		cout << "Impossible" << endl;
    		continue;
    	}
    	gcd(sp, l, g, ans, ans2);
    	if(d % g){
    		cout << "Impossible" << endl;
    		continue;
    	}
    	else{
    	    gcd(sp, l, g, ans, ans2);
    		ans = ans * d / g;
    		ll t = l / g;
    		if (ans >= 0)
    			ans = ans % t;
    		else
    			ans = (ans % t) + t;
    		cout << ans << endl;
    	}
    }
	return 0;
}

 

Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00