转载注明,侵删
题意:
给出 a,b,c,x1,x2,y1,y2,求满足 ax+by+c=0,且 x∈[x1,x2],y∈[y1,y2] 的整数解个数。...求解过程中,扩展欧几里得比欧几里得多了一个赋值过程,具体证明如下:
设 ax1+by1=gcd(a,b),bx2+(a mod b)y2=gcd(b,a mod b)
因为由欧几里得算法可知,gcd(a...+1)*(y2-y1+1);
当 a=0 b≠0 时:
此时即为求解 by=c,则 y=c/b,
如果 c/b 不是整数或 c/b 不在 [y1,y2] 的范围内,无解
否则 [x1,x2]...对于本道题,首先要注意的是,对于负数的模运算在此算法中无法得到正确解,所以要处理一下 a,b,c 的正负情况。 如果 a 为负数,只需将 a 取相反数后,再处理一下 x∈[x1,x2] 的范围。...-kb的整数 k 的个数 但是在求解这两个一次函数的过程中,会有除不尽的现象,该如何取整呢?