[SGU106 The Equation]【欧几里得拓展算法解二元一次方程】

【题目大意】

给定ax+by+c=0。求x1<=x<=x2 && y1<=y<=y2的解有多少组。

【算法分析】

见到缺了这种例题，又没A这题，那么就做一下。

例题系列。

首先判断掉a和b中存在0的情况。然后exgcd解出ax+by=gcd(a,b)的一个初始解，

然后假如-c%gcd(a,b)!=0。那么无解。否则a/=g b/=g c/=g。然后x就只能+-b，y对应地+-a。然后用个除法搞一下就可以了。

一开始我后面取范围用倍增算法，就是2进制步长那种跨越的。第3个点居然就TLE了= =。

【时间复杂度】O(lg (x+y))

【空间复杂度】O(1)

【CODE】

#include