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可能是负数或者； 这个时候再搞一下就好了；
#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define Ll long longusing namespace std;Ll x,y,n,m,l,ans;Ll gcd(Ll x,Ll y){return y?gcd(y,x%y):x;}void exgcd(Ll a,Ll b,Ll &x,Ll &y){ if(!b){x=1;y=0;return;} exgcd(b,a%b,x,y); int X=x; x=y; y=X-a/b*y;}int main(){//其实x,y一开始要-1的，因为是膜域，但是因为我们算差，所以不用管 scanf("%lld%lld%lld%lld%lld",&x,&y,&n,&m,&l); int a=0,b=l,c=0;// a=((m-n)%l+l)%l;//这里两种都行// c=((x-y)%l+l)%l; a=((n-m)%l+l)%l; c=((y-x)%l+l)%l; int g=gcd(a,b); if(c%g){PRintf("Impossible");return 0;} exgcd(a,b,x,y); x=x*c/g; l=l/g;//这里ax+by=c的b就是l x=(x%l+l)%l;//x>=0且最优 printf("%d",x);}新闻热点
疑难解答
