扩展欧几里得模板套一下就A了，不过要注意刚好整除的时候，代码中有注释

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;typedef long long ll;ll exgcd(ll a, ll b, ll&x, ll&y) {   if (b == 0) {       x = 1;       y = 0;       return a;   }   ll r = exgcd(b, a%b, y, x);   ll t = x;   y = y - a/b*t;   return r;}bool modular_linear_equation(ll a, ll b, ll n) {    ll x, y, x0, i;    ll d = exgcd(a, n, x, y);    if (b%d)    {        printf("Impossible\n");        return false;    }    x0 = x*(b/d)%n; //x0为方程的一个特解，可以为正也可以为负。题目要求的是最小的非负数    ll ans;    if(x0<0)    {        ans=x0;        for(i = 0;ans<0; i++)            ans=(x0 + i*(n/d))%n;    }    else if(x0>0)    {        ans=x0;        ll temp;        for(i=0;ans>=0;i++)        {            temp=ans;            ans=(x0 - i*(n/d))%n;        }        ans=temp;    }    else        ans=n; //此时x0=0，但是结果一定会大于0，所以要加一个n    printf("%I64d\n",ans);    return true;}int main(){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    ll x,y,m,n,L;    while(~scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&L))    {        ll temp1=m-n,temp2=y-x;        if(temp1<0)        {            temp1=-1*temp1;            temp2=-1*temp2;        }        modular_linear_equation(temp1,temp2,L);    }    return 0;}

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;typedef long long ll;ll exgcd(ll a, ll b, ll&x, ll&y) {   if (b == 0) {       x = 1;       y = 0;       return a;   }   ll r = exgcd(b, a%b, y, x);   ll t = x;   y = y - a/b*t;   return r;}bool modular_linear_equation(ll a, ll b, ll n) {    ll x, y, x0, i;    ll d = exgcd(a, n, x, y);    if (b%d)    {        printf("Impossible\n");        return false;    }    x0 = x*(b/d)%n; //x0为方程的一个特解，可以为正也可以为负。题目要求的是最小的非负数    ll ans;    if(x0<0)    {        ans=x0;        for(i = 0;ans<0; i++)            ans=(x0 + i*(n/d))%n;    }    else if(x0>0)    {        ans=x0;        ll temp;        for(i=0;ans>=0;i++)        {            temp=ans;            ans=(x0 - i*(n/d))%n;        }        ans=temp;    }    else        ans=n;    printf("%I64d\n",ans);    return true;}int main(){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    ll x,y,m,n,L;    while(~scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&L))    {        ll temp1=m-n,temp2=y-x;        if(temp1<0)        {            temp1=-1*temp1;            temp2=-1*temp2;        }        modular_linear_equation(temp1,temp2,L);    }    return 0;}

POJ 1061 青蛙的约会 扩展欧几里得