https://vijos.org/p/1009 這個exgcd我 復制 推一遍 對于ax+by=c 我們先算ax+by=(a,b) （這個是最大公約數） 然后把解乘上c/(a,b)即可； 所以顯然當(a,b)|c時有x，y解； 設A = b, B = a mod b。(這個就是普通的gcd哦) 那么考慮方程Ax′+By′=(a,b), 也就是bx′+(a %b)y′=(a, b) 假如我們求出了x’,y’怎么求x，y； a%b=a-a/b*b（a/b下取整）拆開再合并就是 ay′+b(x′??a/b? y′)=(a,b) 所以答案就是 x=y′, y=x′ ??a/b? y′ 那我們怎么求x’,y’ 可以遞歸； 遞歸到最后b就會是0，這個跟gcd是一樣的

不過出題人可以卡long long，所以要快速乘，當然這個是毒瘤題； http://blog.csdn.net/Fop_zz/article/details/55000973 這里的exgcd更簡短，但本質是一樣的； 還有，比如ax+by=c; 那么對于x 兩個相鄰的解相差b/gcd(a,b) 因為 ax+by=c等價于a(x+b)+b(y-a)=c;

這道題我們可以這樣； 我們設走k步; x+kn=y+km（mod l） 后面的括號是膜域； 就是在0~l-1的范圍里； 然后我們可以再設一個kk代表(x+kn)/l 就是走了幾圈； 然后就變成了 k(n-m)-kkl=y-x; 這個和ax+by=c一樣的； 然后exgcd好了； 求出來x后要乘(c/gcd(a,b))，這個在上面解釋了； 但是x可能是負數或者； 這個時候再搞一下就好了；