我的模方程求解过程哪里错了呢?(代码有注释)
查看原帖
我的模方程求解过程哪里错了呢?(代码有注释)
1740609
lqy202400091楼主2025/8/30 18:22

这是我照抄《算法导论》的模板,不知哪里错了。哪位大佬可以“传道授业解惑”?余不耻相师。

#include<cstdio>
#define long long long
long x,y,m,n,L;
long gcd(long a,long b,long &x,long &y);
int main()
{
    scanf("%ld %ld %ld %ld %ld",&x,&y,&m,&n,&L);
    long v=m>n?(m-n)%L:(n-m)%L,s=(L+x-y)%L;
    long d,x_,y_;
    
    //求解模方程 (m-n)t≡x-y (mod L).
    d=gcd(v,L,x_,y_);
    if(s%d)
    {
        printf("Impossible");
        return 0;
    }
    long min=(x_*(s/d))%L;
    for(int i=1,x=min,y=n/d;i<d;++i)
    {
        x=(x+y)%L;
        if(x<min)
            min=x;
    }
    printf("%ld",min);
}

long gcd(long a,long b,long &x,long &y)//求最大公约数。
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    long d=gcd(b,a%b,x,y);
    long t=x-(a/b)*y;
    x=y,y=t;
    return d;
}
2025/8/30 18:22
加载中...