bzoj1477: 青蛙的约会（exgcd）

　　昨天打code+的时候发现自己已经不大会exgcd了。。赶紧复习一下QAQ

求$ax+by=gcd(a,b)$的解

　　初始条件

$gcd(a, 0)=a$

$x=1,y=0$

　　推导过程

$gcd(a,b)=gcd(b,a\%b)$

$ax'+by'=bx+(a-left lfloor frac{a}{b} ight floor *b)y$

$ax'+by'=ay+bx-left lfloor frac{a}{b} ight floor *by$

$ax'+by'=ay+b(x-left lfloor frac{a}{b} ight floor *y)$

$x'=y,y'=x-left lfloor frac{a}{b} ight floor *y$

　　然后大概就完了

　　对于求$ax+by=c$的话，先求$ax+by=gcd(a,b)$的一个解$x_0,y_0$，则$x'=x_0*c/d,y'=y_0*c/d$即为$ax+by=c$的一个解，因为$d*c/d=c$嘛，显然...注意如果不满足$gcd(a,b)|c$就无解，更相减损术可证。

　　设$d=gcd(a,b)$。求出$ax+by=c$的一个整数解$x_0,y_0$后，其他整数解可以用$x_0-b/d,y_0+a/d$求得。因为显然$a(x_0-b)+b(y_0+a)=c$是满足的，但是其实最小的间隔应该要除以最大公约数，所以$a(x_0-b/d)+b(y_0+a/d)=c$也是成立的。

ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(!b) return x=1, y=0, a;
    int ans=exgcd(b, a%b, x, y);
    ll t=x; x=y; y=t-a/b*y;
    return ans;
}

View Code

　　要求得最小正整数解，就是要求$(((x_0\% |b/d|)+|b/d|)\%|b/d|)$，然后这题就完了。

#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=500010, inf=1e9; ll X, Y, m, n, L, a, b, c, d, x, y, p; inline void read(ll &k) { int f=1; k=0; char c=getchar(); while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar(); while(c<='9' && c>='0') k=k*10+c-'0', c=getchar(); k*=f; } ll exgcd(ll a, ll b, ll &x, ll &y) { if(!b) return x=1, y=0, a; int ans=exgcd(b, a%b, x, y); ll t=x; x=y; y=t-a/b*y; return ans; } int main() { read(X); read(Y); read(m); read(n); read(L); a=m-n; b=L; c=Y-X; d=exgcd(a, b, x, y); if(c%d!=0) return puts("Impossible"), 0; x=x*(c/d); b/=d; p=b>0?b:-b; x=((x%p)+p)%p; x+=x?0:p; printf("%lld ", x); }

bzoj1477: 青蛙的约会（exgcd）

相关推荐