POJ 1061 青蛙的约会

各大题解里说明了是求ax+by=c的解集

使用拓展欧几里德算法可以求ax+by=易做图(a,b)的解集。

设g=易做图(a,b)

由于a、b、x、y均为整数，那么假如c|g则有解，否则无解

可以求得a*x0 + b*y0 =g 的一组特解x0,y0

那么通过对等式两边同乘c/g可以得到a*x0*c/g + b*y0*c/g = c

也就是说我们找到了一组原式的特解x=x0*c/g ，y=y0*c/g。

通过对原式稍加修改得到a*(x+k*b) + b*(y-k*a) = c，其中k为任意整数

可以发现x+k*b ，y-k*a仍然为一组解，也就是说我们得到了通解。

那么如何得到最小的正整数x呢？

可以看到，a,b,x,y均为已知常量，而k的增加（减少）相当于增加（减少）了若干个b

思考一下对x对b取模的形式，可以想到x + k*b完全就是x mod b的所有解，

那么最小正整数x就是使得x mod b>=0的第一个值，即( (x0*c/g)%b +b)%b。

此题中需要注意使易做图(a,b)为正

<span style="font-size:18px">#include<cstdio>  
typedef long long ll;  
ll ext_易做图(ll a,ll b,ll &x,ll &y){  
    if(b==0){x=1;y=0;return a;}  
    ll r=ext_易做图(b,a%b,y,x);  
    y-=x*(a/b);return r;  
}  
void swap(ll& a,ll& b){  
    ll t=a;a=b;b=t;  
}  
int main(){  
    ll g,x,y,n,m,l,t,p;  
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);  
    if(n<m){swap(x,y);swap(n,m);}  
    g=ext_易做图(n-m,l,t,p);  
    x-=y;  
    if(x%g)puts("Impossible");  
    else{  
        t=t*x/g;  
        t=(t%l+l)%l;  
        printf("%lld\n",t);  
    }  
    return 0;  
}  
</span>  


<span style="font-size:18px">#include<cstdio>  
typedef long long ll;  
ll ext_易做图(ll a,ll b,ll &x,ll &y){  
    if(b==0){x=1;y=0;return a;}  
    ll r=ext_易做图(b,a%b,y,x);  
    y-=x*(a/b);return r;  
}  
void swap(ll& a,ll& b){  
    ll t=a;a=b;b=t;  
}  
int main(){  
    ll g,x,y,n,m,l,t,p;  
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);  
    if(n<m){swap(x,y);swap(n,m);}  
    g=ext_易做图(n-m,l,t,p);  
    x-=y;  
    if(x%g)puts("Impossible");  
    else{  
        t=t*x/g;  
        t=(t%l+l)%l;  
        printf("%lld\n",t);  
    }  
    return 0;  
}  
</span>

补充：软件开发 , C++ ,