T1
https://www.cnblogs.com/qxyzili--24/p/11226220.html
#include<bits/stdc++.h> #define ll long long #define PZ printf("ZenMeZheMeDuo ") using namespace std; const int maxn=1100; ll t,a,b,c,x,y,g; int exgcd(ll a,ll b,ll &x,ll &y){ if(b==0){ x=1,y=0; return a; } int g=exgcd(b,a%b,y,x); y-=(a/b)*x; return g; } int main(){ scanf("%lld",&t); while(t--){ scanf("%lld%lld%lld",&a,&b,&c); // if(a==1&&b==1){ // if(c<=65536) printf("%lld ",max((ll)0,c-1)); // else PZ; // continue; // } // if(a+b==c) {printf("1 ");continue;} if(a==0&&b==0){ if(c==0) PZ; else printf("0 "); continue; } // if(a==0){ // if(c%b==0) PZ; // else printf("0 "); // continue; // } // if(b==0){ // if(c%a==0) PZ; // else printf("0 "); // continue; // } // if(c==0) if((a>0&&b>0)||(a<0&&b<0)) {printf("0 ");continue;} // if((a>0&&b>0)||(a<0&&b<0)&&((a>0&&c<0)||(a<0&&c>0))) {printf("0 ");continue;} /******************************分割线（以下是重点_扩欧）*********************************/ bool aa=0,bb=0; if(c<0) c=-c,b=-b,a=-a; if(a<0) a=-a,aa=1; if(b<0) b=-b,bb=1; g=exgcd(a,b,x,y); if(c%g!=0) { printf("0 "); continue; } x*=c/g; y*=c/g; if(a*x+b*y!=c) { printf("0 "); continue; } if(aa) a=-a,x=-x; if(bb) b=-b,y=-y; if(!a) { if(y>0) PZ; else printf("0 "); continue; } if(!b) { if(x>0) printf("ZenMeZheMeDuo "); else printf("0 "); continue; } if((a>0&&b<0)||(a<0&&b>0)) {PZ;continue;} if(a<0) a=-a,b=-b,c=-c;//使a,b,c全为正 a/=g,b/=g,c/=g; x%=b; while(x<=0) x+=b; y=(c-x*a)/b;//x最小，y最大 ll y1=y%a; while(y1<=0) y1+=a;//x最大，y最小 if(y1>y){printf("0 ");continue;} ll ans=(y-y1)/a+1; if(ans>65535) PZ; else {printf("%lld ",ans);} } return 0; }