ouuan 的博客

ouuan 的博客

题解 P1082 【同余方程】

posted on 2018-02-07 16:41:14 | under 题解 |

感觉还没有人讲到为什么是exgcd(x,y,a,b)而不是exgcd(x,y,a,-b)

如果又是我看漏了的话..反正题解是写给自己看的


错误思路:

由ax ≡ 1 (mod b)得ax=by+1

移项得:ax-by=1

于是天真的我一开始写的exgcd(x,y,a,-b),各种WA


先讲为什么可以exgcd(x,y,a,b):

其实一句话就可以说明,令y'=-y,ax+by'=ax-by,而本题只求x


然后是为什么不能exgcd(x,y,a,-b):

因为这题是基于gcd(a,y的系数(正解中的b,错解中的-b))=1的

而gcd(a,b)当b为负数时,可以举例看一下

gcd(12,-7)=gcd(-7,5)=gcd(5,-2)=gcd(-2,1)=gcd(1,0)=1

gcd(17,-5)=gcd(-5,2)=gcd(2,-1)=gcd(-1,0)=-1

可以看出,结果是1还是-1和gcd次数的奇偶有关,因此会出现大量WA


总结:使用exgcd时要注意a,b为正,求解ax=by+1(a,b为互质正整数)的解集时,要先求出ax+by=1的解集A',那么所求解集即为A{(x,y)|(x,-y)∈A'}


毕竟是题解..还是给份完整代码

#include <iostream>

using namespace std;

void exgcd(int& x,int& y,int a,int b);

int main()
{
    int a,b,d,x,y,k;

    cin>>a>>b;

    exgcd(x,y,a,b);

    while (x<0)
    {
        x+=b;
    }

    cout<<x%b;

    return 0;
}

void exgcd(int& x,int& y,int a,int b)
{
    if (b==0)
    {
        x=1;
        y=0;
    }
    else
    {
        exgcd(y,x,b,a%b);
        y-=a/b*x;
    }
}