[ACM] POJ1061解题报告

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

#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;
}

Leave a Reply

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