扩展欧几里德，ap+bq=c，此题中
a=m-n;
b=-l;
c=y-x;
递归到当b=0是停止此时p一定为1，q值不定，不妨设为0，再递归上去得到p0，然后通解是
p = p0 + b/Gcd(a, b) * t
q = q0 – a/Gcd(a, b) * t
此处有一个小问题 导致了我一直不能AC
设c是gcd的n倍，那么p0*=n，然而后面b/Gcd(a, b) * t要不要乘以n呢，答案是不要，没搞清楚为什么，反正不乘就过了..
1 | #include <cstdio> |
2 | #include <cmath> |
3 | /* p = p0 + b/Gcd(a, b) * t |
4 | q = q0 - a/Gcd(a, b) * t |
5 | 45 165 63 22 10000 */ |
6 |
7 | __int64 d; |
8 |
9 | void exgcd(__int64 *p,__int64 *q,__int64 a,__int64 b) { |
10 | __int64 x,y; |
11 | if(!b) { |
12 | *p=1; |
13 | *q=0; |
14 | d=a; |
15 | return; |
16 | } |
17 | exgcd(&x,&y,b,a%b); |
18 | *p=y; |
19 | *q=(x-a/b*y); |
20 | return; |
21 | } |
22 |
23 | int main() { |
24 | __int64 x,y,m,n,l,a,b,c,p,q,t; |
25 | scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l); |
26 | a=m-n; |
27 | b=-l; |
28 | c=y-x; |
29 | exgcd(&p,&q,a,b); |
30 | if(c%d) { |
31 | printf("Impossible\n"); |
32 | return 0; |
33 | } |
34 | n=c/d; |
35 | t=(b/d); |
36 | t=t>0?t:-t; |
37 | p=(n*p%t+t)%t; |
38 | printf("%I64d\n",p); |
39 | return 0; |
40 | } |
