over 4 years ago

什么都忘了啊啊啊啊啊啊

其实就是求ax+by=l的式子

从讨论版1000组数据里发现了一个bug

当x0-y0是l的倍数的时候,此时化简后的等式变为ax=0

由于扩欧做逆元求的是x+y绝对值的最小解,所以x会变为零。需要特判!!!

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll  long long
using namespace std;
ll x0,y0,m,n,l;
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    if (!b) {x=1;y=0;d=a;}
    else {ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
ll gcd(ll x,ll y)
{
    if (x%y==0) return y;else return gcd(y,x%y);
}
ll inv(ll a,ll n)
{
    ll d,x,y;
    ex_gcd(a,n,d,x,y);
    return (x+n)%n;
}
int main()
{
    ll d,a,b,p;
    long long resulta,resultb;
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    while (scanf("%lld%lld%lld%lld%lld",&x0,&y0,&m,&n,&l)!=EOF)
    {
    a=n-m;b=l;p=x0-y0;
    while (a<0) a+=l;
    while (p<0) p+=l;
    d=gcd(a,b);
    if (p%d==0)
    {
        a=a/d;b=b/d;p=p/d;
        ll x=p*inv(a,b)%b;
        if (x==0) x=b;
        printf("%lld\n",x);
    }
    else printf("Impossible\n");
    }
}
← 【bzoj2434】【ac自动机】【fail树】【dfs序树状数组】阿狸的打字机 【bzoj2594】【lct】水管局长数据加强版 →
 
comments powered by Disqus