# Extended Euclidean solution of the equation

Topic encryption

First of all, we can think of using exgcd when we see this problem, but how to use it? We know that as soon as this equation has a bunch of solutions, then the limit of this problem is the number of solutions. We think that if we simplify the equation, we can get $y=\frac{c}{b}-\frac{a}{b}*x$, and then we will use the knowledge of compulsory education. When a and b are different, they must be the same. If exgcd has solutions, they must be the same. It's an infinite group. It's a direct verdict. If we consider a b's identity sign, then we can get a decreasing straight line that must pass through the first quadrant. We do the following operations on the equation: $a(x-b)+b(y+a)=c$. Obviously, it is also true. At this time, ab can be transformed into a positive sign. If x decreases, then y increases. We can get the maximum solution of Y by moduling x to b, then get the minimum solution of Y by moduling y to a, and then the transformation of y must be a sequence of equal difference numbers. If the tolerance is a, then the range of y can be found and the proposition can be solved.

And then I'll give you A special judgment. Read it and remember to type A minus sign.

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll rd()
{
ll s=0,w=1;
char cc=getchar();
while(cc<'0'||cc>'9') {if(cc=='-') w=-1;cc=getchar();}
while(cc>='0'&&cc<='9') s=(s<<3)+(s<<1)+cc-'0',cc=getchar();
return s*w;
}
ll exgcd(ll a,ll b,ll &x,ll &y,ll c)
{
if(b==0){x=c/a;y=0;return a;}
ll d=exgcd(b,a%b,y,x,c);
y-=a/b*x;
return d;
}
int main()
{
//    freopen("data.in","r",stdin);
//freopen("data.ans","w",stdout);
ll T=rd(),a,b,c,x,y,g,ans;
while(T--)
{
a=rd(),b=rd(),c=rd();
//cout<<a<<" "<<b<<endl;
if(!a&&!b)
{
if(!c)printf("ZenMeZheMeDuo\n");
else printf("0\n");
continue;
}
if(a<0&&b<0) a=-a,b=-b,c=-c;
g=exgcd(a,b,x,y,c);
if(c%g){puts("0");continue;}
if(a==0)
{
if((b<=0&&c>=0)||(b>=0&&c<=0))printf("0\n");
else printf("ZenMeZheMeDuo\n");
continue;
}
if(b==0)
{
if((a<=0&&c>=0)||(a>=0&&c<=0))printf("0\n");
else printf("ZenMeZheMeDuo\n");
continue;
}
if(a*b<0)
{
printf("ZenMeZheMeDuo\n");
continue;
}
if(a<0&&b<0)a=-a,b=-b,c=-c;
a/=g;b/=g;c/=g;x%=b;
while(x<=0)x+=b;
y=(c-a*x)/b;
ll ymin=y%a;while(ymin<=0)ymin+=a;
if(ymin>y)ans=0;
else ans=(y-ymin)/a+1;
if(ans>65535)printf("ZenMeZheMeDuo\n");
else printf("%lld\n",ans);
}
}
/*
g++ 6.cpp -o 6
./6
4
1 -1 3
1 1 65536
1 1 65537
2 3 24
*/

Keywords: PHP

Added by xzazx on Thu, 17 Oct 2019 21:58:19 +0300