你是想说同余符号吗
by cff_0102 @ 2023-04-23 12:01:25
为什么我感觉a是可以小于零的
by cff_0102 @ 2023-04-23 12:02:22
@[cff_0102](/user/542457) 是同余号，但是我的实现中 $a<0$ 就会出错
```
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
LL p,q,c,a,b,l,d;
void exgcd(LL a,LL b,LL &x,LL &y) {
if(!b) {
x=1; y=0;
d=a;
return ;
}
exgcd(b,a%b,y,x); y-=(a/b)*x;
return ;
}
int main () {
scanf("%lld%lld%lld%lld%lld",&p,&q,&a,&b,&l);
c=q-p;
a=(a-b);
b=l;
if(a<0) a=(a%l+l)%l; //这句话屏蔽掉,就会出错
if(c<0) c=(c%l+l)%l;
LL x,y;
exgcd(a,b,x,y);
if(c%d!=0) {
printf("Impossible");
return 0;
}
x*=c/d; y*=c/d;
a/=d; b/=d;
LL xl;
xl=(x%b+b)%b;
cout<<xl;
return 0;
}
```
by daduoli @ 2023-04-23 14:25:50
是不是欧几里得求最大公约数要为正。
by daduoli @ 2023-04-23 14:31:10
@[cff_0102](/user/542457) 我知道为什么了，[看这个](https://www.luogu.com.cn/discuss/254102)
因为求得的 $d$ 最大公约数可能是负数，导致最后答案是最大负整数解，所以加一个特判即可。
by daduoli @ 2023-04-23 14:42:23