又是一个调不出代码且有点困的颓废晚三，数学能催眠果然没错，鉴于我还是没怎么看明白crt且推不出来组合数，决定写一写T1的题解，我如果能在下课之前写完的话，我就去拿T3暴力模拟的60分，虽然不太可能的样子
T1，照着数据范围，硬搜加各种特判的话，基本60分起，其实我预估的时候觉得怎么着也可以到80，然而自我感觉过于良好，大佬们T1用exgcd跑的贼快，然而我觉得用exgcd去控制范围的话有点麻烦，就没有控制，直接暴力了(本来还以为会T)，虽说我也打了exgcd，但是实际上只用到了gcd，改题的时候由于怕我自己漏掉一些情况，就把abc正负零27种组合都列了一遍，检查自己不重不漏之后就信心满满的交了上去，结果WA80大概调了一个小时，拍了好多数据，结果发现自己很zz，对于a或b等于0时，方程就变成了ax(by)=c，我就自动认为他要么一个解，要么没有解，可事实是要么没有解，要么无穷多组解，其实很显然，因为你有一项系数为0，只要系数不为0的那个项有正整数解，那系数为0那一项就可以随便取值，所以是0或正无穷，需要搜索的只有abc全部同号的情况，所以最后2000多毫跑了过去，考场上想不出来exgcd真的很难受。。。。。。
1 #include<iostream> 2 #include<cstdio> 3 #define ll long long 4 using namespace std; 5 int t,a,b,c,x,y; 6 int exgcd(int a,int b,int &x,int &y) 7 { 8 int G,tmp; 9 if(b==0) {x=1; y=0; return a;} 10 G=exgcd(b,a%b,x,y); 11 tmp=x; x=y; y=tmp-a/b*y; 12 return G; 13 } 14 int main() 15 { 16 //freopen("data.in","r",stdin); 17 //freopen("data.out","w",stdout); 18 scanf("%d",&t); 19 while(t--) 20 { 21 scanf("%d%d%d",&a,&b,&c); 22 if(a==0) 23 { 24 if(b==0) 25 { 26 if(c==0) {printf("ZenMeZheMeDuo "); continue;} 27 else if(c>0) {printf("0 "); continue;} 28 else {printf("0 "); continue;} 29 } 30 if(b<0) {b=-b; c=-c;} 31 if(c==0) {printf("0 "); continue;} 32 else if(c>0) 33 { 34 if((c%b)==0) {printf("ZenMeZheMeDuo "); continue;} 35 else {printf("0 "); continue;} 36 } 37 else {printf("0 "); continue;} 38 } 39 if(a<0) {a=-a; b=-b; c=-c;} 40 if(b==0) 41 { 42 if(c==0) {printf("0 "); continue;} 43 else if(c>0) 44 { 45 if((c%a)==0) {printf("ZenMeZheMeDuo "); continue;} 46 else {printf("0 "); continue;} 47 } 48 else {printf("0 "); continue;} 49 } 50 else if(b>0) 51 { 52 if(c==0) {printf("0 "); continue;} 53 else if(c>0) 54 { 55 if(a==1&&b==1) 56 { 57 int ans=max(0,c-1); 58 if(ans<=65535) {printf("%d ",ans); continue;} 59 else {printf("ZenMeZheMeDuo "); continue;} 60 continue; 61 } 62 else if(a+b==c) {printf("1 "); continue;} 63 else 64 { 65 int ls=exgcd(a,b,x,y); 66 if((c%ls)!=0) {printf("0 "); continue;} 67 int ans=0; 68 for(int i=1;i<=c;++i) 69 { 70 int ls1=c-a*i; 71 if(ls1<b) break; 72 if((ls1%b)==0) ans++; 73 if(ans>=65536) break; 74 } 75 if(ans>65535) {printf("ZenMeZheMeDuo "); continue;} 76 else {printf("%d ",ans); continue;} 77 } 78 } 79 else {printf("0 "); continue;} 80 } 81 else 82 { 83 if(c==0) {printf("ZenMeZheMeDuo "); continue;} 84 else 85 { 86 int ls=exgcd(a,b,x,y); 87 if((c%ls)!=0) {printf("0 "); continue;} 88 else {printf("ZenMeZheMeDuo "); continue;} 89 } 90 } 91 } 92 return 0; 93 }