欧几里德&扩充以及求解线性方程学习总结-附上poj1061解题报告

欧几里德&扩展以及求解线性方程学习总结--附上poj1061解题报告

欧几里德算法：

欧几里德就是辗转相除法，调用这个gcd(a,b)这个函数求解a,b的最大公约数

公式：

gcd(a,b)=gcd(b,a%b)；并且gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|)

代码：

// 132K 32MS#include <stdio.h>#define ll __int64ll x,y,a,b,c,d;ll exgcd(ll a,ll b){    if(!b) {x = 1; y = 0; return a;}    ll d = exgcd(b,a%b);    ll X = x;    x = y;    y = X - a/b*y;    return d;}int main(){    ll X,Y,n,m,L;    while(~scanf("%I64d%I64d%I64d%I64d%I64d",&X,&Y,&m,&n,&L))    {        a = n-m; b = L; c = X-Y;        d = exgcd(a,b);//先得到最大公约数，同时得到一组解x,y        if(c%d != 0)//无解        {            printf("Impossible\n");continue;        }        ll k = b/d;//最小解        x *= (c/d);//        x = (x%k+k)%k;        printf("%I64d\n",x);    }    return 0;}