#include "stdio.h"
#include "stdlib.h"

int gys(int,int);//求最大公约数;
void precheck(int a,int b,int c);//检查输入、化简;
void check(int a,int b,int c,int &n,int &m);//辗转递归;

void main(void) 
{
    int x=1,y=2,m=3,n=4,l=5;
    printf("Input\n");
    scanf("%d %d %d %d %d",&x,&y,&m,&n,&l);
    printf("Output\n");
    precheck(abs(x-y),abs(m-n),l);
}

void precheck(int a,int b,int c)
{
    int n,m,ac,bc,abc;
    int la=a,lb=b,lc=c;
//    printf("--------------------\n",a,b,c);
//    printf("a=%d,b=%d,c=%d\n",a,b,c);
    la%=lc;lb%=lc;
    ac=gys(la,lc);
    bc=gys(lb,lc);
    abc=gys(ac,bc);
    if (bc>abc)//原理A+K*N*X=L*M*X;A，X互质则不成立;
    {
        printf("Impossible\n");
        return;
    }
    if(abc>1)
    {
        la/=abc;lb/=abc;lc/=abc;//a+n*b=m*c;化为最简式；
    }
    check(la,lb,lc,n,m);
    m=m+a/c+n*(b/c);
//    printf("a+(%d+%d*k)*b=(%d+%d*k)*c\n",n,c,m,b);
//    printf("--------------------\n",a,b,c);
    printf("%d\n",n);
}

int gys(int a,int b)
{
    unsigned int t,i;
    a=abs(a);b=abs(b);
    if(a==1)return 1;
    if(b==1)return 1;
    if (a==b)return a;
    if (a>b)
    {
        t=a%b;
        if (t==0)return b;
        i=b;
    }
    else
    {
        t=b%a;
        if (t==0)return a;
        i=a;
    }
    return gys(t,i);
}

void check(int a,int b,int c,int &n,int &m)
{
    if (a+b==c)
    {
        n=1;
        m=1;
    }
    else if (b==1)
    {
        n=c-a;
        m=1;
    }
    else if(a%b==0)
    {
        n=c/gys(b,c)-a/b;
        m=b/gys(b,c);
    }
    else
    {
        int rn,rm;
        check(-a%b,c%b,b,rn,rm);
        m=rn%b;
        n=(rn*(c/b)+rm-a/b)%c;
    }
}

• Re:算法绝对牛Ｂ，怎么说我错了？？？跪求更牛人来解释一下！！！ (574) justkain 2006-08-15 19:45:25
• Re:算法绝对牛Ｂ，怎么说我错了？？？跪求更牛人来解释一下！！！ (24) asdff12 2006-11-14 18:10:00
  • 我靠，我测了几组数据都是错的！！！！！！！！！1 (25) asdff12 2006-11-14 18:10:15