由于遭到警告，没敢粘题目，于是搞了个图片。
这题作为t1，还是蛮简单的
其实刚开始我写这个题解的时候，我还没AC。【但是显然我最后A了
但是烦的不行不想调了。
反正我博客又没人看，于是就先写一写有关的知识点。
其实我在考场上是想到了的，毕竟昨天偶然间翻到了一篇博客。
手玩了一下，发现确实是的。
所以今天我其实本来很开心，觉得至少也有80分了【没考虑到一些细节对我来说很正常的
然后快速的打完了这道题，才过了40分钟，信心满满的去做t2了。
这题一看 ax+by=c
正常人【指学过并且没忘的人 就应该能够意识到是扩展欧几里得。
这里就简单复习一下：
听我讲！
首先，扩展欧几里得就是求解 ax + by = c 的所有整数解的问题。
？？？？？这两个有什么关系呢？
这个时候，我们引入一个定理：裴蜀定理
如果a、b是整数，那么一定存在整数x、y使得 ax+by=gcd(a,b)。
不好理解的话，我们换一种说法：
假设 ax+by=c 成立
已知 ax+by=gcd(a,b)
所以 c一定是gcd(a,b) 的倍数
这样的话，我们现在手里的方程就变成了一个具有gcd 的结果。
那么是不是意味着我们只要能找到一组解，就能全部找出来？
好的，我们先感性理解一下，然后假装这个结论是对的。
要找到一组解，那么就要找到gcd的值。
想到求最大公因数，那么最先想到的就是辗转相除法。
int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
所以，对于gcd而言，我们可以使用 gcd(a,b) = gcd(b, a%b) 这个式子一点一点推到底。
直到b的值成为0，此时最大公因数就是a的值。
好的，我们接下来取出这个过程中的两个式子（就拿第一个和第二个举例吧）
a * x1 + b * y1 = gcd(a,b)
b * x2 + (a%b) * y2 = gcd(b,a%b)
这两个式子有什么关系呢？
可以发现，只要能够建立起来x1与x2，y1与y2的关系，我们就可以得到一组解。
a * x1 + b * y1 = b * x2 + (a%b) * y2
？？？？我不会处理模的问题啊？怎么办呢？
算法是死的，人是活的。
我们可以尝试 把a%b换成a-(a/b)*b
那么式子就变成了这样 a * x1 + b * y1 = b * x2 + (a - (a / b) * b) * y2
解得 x1 = y2 y1 = x2 - (a / b) * y2
好的，那么这个问题就解决了。
对于方程a * x + b * y = gcd(a,b)，我们可以不断的往下变成b * x + (a % b) y = gcd(a,b) ；
按照欧几里得的过程，b会变成0，即此时方程a * x + b * y = gcd(a,b)
因为b = 0，变成了a * x = gcd(a,b) ，此时a就等于gcd(a,b)
所以由原方程往下推了N次的方程 a * x = gcd(a,b) 来说，得到一个解x = 1, y = 0。
所以如果得到了这个方程的解，再回溯回去，就可以得出原方程 a * x + b * y = gcd(a,b) 的一个特解。
现在我们要开始思考，怎么样才能通过一组解找到全部的解呢？
我们知道：
对于关于x，y的方程a * x + b * y = c 来说，让x增加b/c，让y减少a/c，等式两边还相等。
？？？？需要我解释一下吗？
对于x来说，增加了b/c，那么加号左边就增加了a*b/c
同样，对于y来说，减少了a/c，那么加号右边就减少了a*b/c
显然是等价的，不影响等号成立。
那么我们就可以通过增加和减少，逐步确定出所有的解。
啊我好像知道自己为什么TLE了
最后，有关a * x + b * y = gcd(a,b)这个方程，是一定有无数组解的。这就不用解释了吧。
附上代码。
void exgcd(ll a,ll b,ll c,ll &x,ll &y,ll &g) { if(!b) { g=a; y=0; x=c/a; } else { exgcd(b,a%b,c,y,x,g); y-=(a/b)*x; } return; }
这道题细节还是蛮多的，不然我也不会爆炸QAQ
其实最有用的并不是exgcd，而是特判。特判全了之后，普通的gcd还有60分，不像我30分滚蛋
1、若a或b等于0 看不为零的是否整除c 若c为0 看a,b是否异号；
2、若两者为负就转化为一者为负；
3、若a,b异号，假设a<0,b>0 则循环x至多b次；
4、若a,b同号但不与c同号，则方程无解 由此若a,b,c均为负就可以全部化为正；
以上为特殊情况，答案只可能是0或者无穷多。
以下情况中，a,b,c均为正数。
1、枚举x，从1开始，满足c-ax>=0,寻找某一时刻(c-ax)%b==0,则找到了方程的一组解；
2、这一组解一定是 x最小 y最大 的那组解，对于相邻的每两组解，y都减去了a和b的最小公倍数除以b，观察y能够减去多少个这个数；
再注意特判，注意处理负数情况即可。
这些是我翻看了很多博客之后总结出来的，参考参考就ok。
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; void exgcd(ll a,ll b,ll c,ll &x,ll &y,ll &g) { if(!b) { g=a; y=0; x=c/a; } else { exgcd(b,a%b,c,y,x,g); y-=(a/b)*x; } return; } int main() { int t; scanf("%d",&t); while(t--) { ll a,b,c,x,y,sum,g; scanf("%lld%lld%lld",&a,&b,&c); if(!a&&!b) { if(!c) printf("ZenMeZheMeDuo\n"); else printf("0\n"); continue; } // if(c<0) { // if(a>0) // aa=1; // else // a=-a; // if(b>0) // bb=1; // else // b=-b; // c=-c; // } if(c<0) {//特判负数，系数全部转正 a=-a; b=-b; c=-c; } bool aa=0; if(a<0) { a=-a; aa=1; } bool bb=0; if(b<0) { b=-b; bb=1; } exgcd(a,b,c,x,y,g);//搞一组解 if(a*x+b*y!=c) { printf("0\n"); continue; } if(aa) { x=-x; a=-a; } if(bb) { y=-y; b=-b; }//搞回来负数 if(!a) { if(y>0) printf("ZenMeZheMeDuo\n"); else printf("0\n"); continue; } if(!b) { if(x>0) printf("ZenMeZheMeDuo\n"); else printf("0\n"); continue; } if((a<0&&b>0)||(a>0&&b<0)) { printf("ZenMeZheMeDuo\n"); continue; } if(a<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 y1=y%a;//最小值 while(y1<=0) y1+=a; int ans=0; if(y1>y) { printf("0\n"); continue; } else ans=(y-y1)/a+1; if(ans>65535) printf("ZenMeZheMeDuo\n"); else printf("%d\n",ans); } return 0; } /** 3 -1 -1 -3 1 1 65536 1 1 65537 **/
AC！！！！！！！！！！！
原文：https://www.cnblogs.com/qxyzili--24/p/11226220.html