不定方程求解

_hxh @ 2024-09-19 20:36:57

by Joe2011 @ 2024-09-19 21:24:08

@_hxh O(c\log^2c) 的样子

by Joe2011 @ 2024-09-19 21:24:33

@Joe2011 然后预处理平方数直接去掉一个log

by _hxh @ 2024-09-19 21:24:45

@Joe2011 可以给我看看吗？

by _hxh @ 2024-09-19 21:25:10

@Joe2011 核心代码就可以了

by Joe2011 @ 2024-09-19 21:27:35

乱写的，凑合着看吧。。。

    ll a,b,c,x,y;IndEquSolTwoOneOneErrOne:cout<<"Please type in your a,b,c(|a|,|b|,|c|<=1000000000) here:";cin>>a>>b>>c;
    if (a==0||b==0||c==0){cout<<"ERROR: CANNOT BE ZERO\n";goto IndEquSolTwoOneOneErrOne;}
    if (abs(a)>1e9||abs(b)>1e9||abs(c)>1e9){cout<<"ERROR: CANNOT BE OVER A BILLION\n";goto IndEquSolTwoOneOneErrOne;}
    char s[2]={'a'},t[2]={'b'};
    ll d=exgcd(a,b,x,y,s,t);
    cout<<"So, a special answer of ax+by=(a,b) is:\n";
    printf("%lld\t*\t%lld\t+\t%lld\t*\t%lld\t=\t%lld\n",a,x,b,y,d);
    cout<<"| Bezout's lemma:\n| when there is a solution of ax+by=c, c must be a multiple of (a,b).\n| when c is a multiple of (a,b), ax+by=c have a solution.\n";
    printf("Your given c=%lld mod (%lld,%lld) has a remainder %lld.\n",c,a,b,c%d);
    if (c%d){cout<<"There is no solution.\n";goto IndEquSolTwoOneOneNos;}
    x=x*c/d,y=y*c/d;
    cout<<"So, a special solution of ax+by=c is:\n";
    printf("%lld\t*\t%lld\t+\t%lld\t*\t%lld\t=\t%lld\n",a,x,b,y,c);
    cout<<"We write it in a normal form:\n";
    printf("/x=%lld\n\\y=%lld\n",x,y);
    cout<<"But we want to make it more beautiful, so we get another special solution:\n";
    while (x<0) x+=b/d,y-=a/d;
    while (x>0) x-=b/d,y+=a/d;
    x+=b/d,y-=a/d;
    printf("/x=%lld\n\\y=%lld\n",x,y);
    cout<<"Then, we can easily get the general solution:\n";
    printf("/x=%lld",x);print(b/d);puts("k");
    printf("\\y=%lld",y);print(-a/d);puts("k");
    IndEquSolTwoOneOneNos:;

by _hxh @ 2024-09-19 21:28:17

@Joe2011 好的，感谢

by Joe2011 @ 2024-09-19 21:28:25

@_hxh 你可以把那些乱七八糟的删掉

by _hxh @ 2024-09-19 21:28:40

此贴结

by _hxh @ 2024-09-19 21:31:12

@Joe2011 关系不大，我只是想学这种解法的思路和具体细节

by _hxh @ 2024-09-19 21:32:09

@Joe2011 感谢