模板--HihoCoder --1297--扩展欧几里得

HihoCoder --1297--扩展欧几里得

求最大公倍数与不定方程的解；

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;
}
void extgcd(LL a,LL b,LL &x, LL &y){if(b){extgcd(b,a%b,y,x);y-=(a/b)*x;}else  x=1,y=0;
}

完整代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
LL s1,s2,v1,v2,m;
LL A,B,C,D;
LL x,y;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;
}
void extgcd(LL a,LL b,LL &x, LL &y){if(b){extgcd(b,a%b,y,x);y-=(a/b)*x;}else  x=1,y=0;
}
int main(){scanf("%lld%lld%lld%lld%lld",&s1,&s2,&v1,&v2,&m);A=v1-v2;B=m;C=s2-s1;if(A<0)	A=A+m;D=gcd(A,B);if(C%D){printf("-1\n");return 0;} A=A/D;B=B/D;C=C/D;//缩小范围 extgcd(A,B,x,y);x=x*C%B;if(x<0)x=x+B;printf("%lld\n",x); return 0;
}