[ACM] POJ1061解题报告

104 Replies

扩展欧几里德，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呢，答案是不要，没搞清楚为什么，反正不乘就过了..

[c]
#include <cstdio>
#include <cmath>
/* p = p0 + b/Gcd(a, b) * t
q = q0 – a/Gcd(a, b) * t
45 165 63 22 10000 */

__int64 d;

void exgcd(__int64 *p,__int64 *q,__int64 a,__int64 b) {
__int64 x,y;
if(!b) {
*p=1;
*q=0;
d=a;
return;
}
exgcd(&x,&y,b,a%b);
*p=y;
*q=(x-a/b*y);
return;
}

int main() {
__int64 x,y,m,n,l,a,b,c,p,q,t;
scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l);
a=m-n;
b=-l;
c=y-x;
exgcd(&p,&q,a,b);
if(c%d) {
printf("Impossible\n");
return 0;
}
n=c/d;
t=(b/d);
t=t>0?t:-t;
p=(n*p%t+t)%t;
printf("%I64d\n",p);
return 0;
}
[/c]

104 thoughts on “[ACM] POJ1061解题报告”

Leave a Reply

Your email address will not be published. Required fields are marked *