• 求解同余方程 数论 扩展欧几里得


    题面:
    在这里插入图片描述
    在这里插入图片描述
    思路:
    a ⋅ x = b ⋅ y + 1 a ⋅ x − b ⋅ y = 1 因为y的取值是任意的,因此可以将这个式子看成: a ⋅ x + b ⋅ y = 1 因为题目保证有解,所以a和b是互质的,即 gcd ⁡ ( a , b ) = 1 而扩展欧几里得就是用来求形如: a ⋅ x + b ⋅ = c 的不定方程的整数解的 这里需要再补充一个裴蜀定理: 若 a , b 为整数,那么一定存在 a ⋅ x + b ⋅ y = gcd ⁡ ( a , b ) 即 a ⋅ x + b ⋅ y 的值一定是 gcd ⁡ ( a , b ) 的倍数 先考虑边界情况 a ⋅ 1 + b ⋅ 0 = gcd ⁡ ( a , b ) , 此时, x = 1 , y = 0 然后考虑一般情况,假设某一次得到的解是 x 0 、 y 0 b ⋅ x 0 + ( a   m o d   b ) ⋅ y 0 = gcd ⁡ ( a , b ) b ⋅ x 0 + ( a − ⌊ a b ⌋ ⋅ b ) ⋅ y 0 = gcd ⁡ ( a , b ) a ⋅ y 0 + b ⋅ ( x 0 − ⌊ a b ⌋ ⋅ y 0 ) = gcd ⁡ ( a , b ) 由此可得: x = y 0 , y = x 0 − ⌊ a b ⌋ ⋅ y 0 已知任意一组解 x 0 , y 0 通解为: x = x 0 + b gcd ⁡ ( a , b ) ⋅ n x = x 0 + b gcd ⁡ ( a , b ) ⋅ n a\cdot x=b\cdot y +1\\ a\cdot x-b\cdot y =1\\ \text{因为y的取值是任意的,因此可以将这个式子看成:}\\ a\cdot x+b\cdot y =1\\ \text{因为题目保证有解,所以a和b是互质的,即}\gcd(a,b)=1\\ \text{而扩展欧几里得就是用来求形如:} a\cdot x+b\cdot=c\text {的不定方程的整数解的}\\ \text{这里需要再补充一个裴蜀定理:}\\ \text{若}a,b\text{为整数,那么一定存在}a\cdot x+b\cdot y=\gcd(a,b)\\ \text{即}a\cdot x+b\cdot y \text{的值一定是}\gcd(a,b)\text{的倍数}\\ \text{先考虑边界情况}a\cdot 1+b\cdot 0=\gcd(a,b),\text{此时,}x=1,y=0\\ \text{然后考虑一般情况,假设某一次得到的解是}x_0、y_0\\ b\cdot x_0+(a\bmod b)\cdot y_0=\gcd(a,b)\\ b\cdot x_0+(a-\lfloor \frac a b \rfloor\cdot b)\cdot y_0=\gcd(a,b)\\ a\cdot y_0+b\cdot (x_0-\lfloor \frac a b \rfloor\cdot y_0)=\gcd(a,b)\\ \text{由此可得:} x=y_0 ,y=x_0-\lfloor \frac a b \rfloor\cdot y_0\\ \text{已知任意一组解}x_0,y_0\text{通解为:} \\ x=x0+ \frac{b} {\gcd (a,b)}\cdot n\\ x=x0+ \frac{b} {\gcd (a,b)}\cdot n\\ ax=by+1axby=1因为y的取值是任意的,因此可以将这个式子看成:ax+by=1因为题目保证有解,所以ab是互质的,即gcd(a,b)=1而扩展欧几里得就是用来求形如:ax+b=c的不定方程的整数解的这里需要再补充一个裴蜀定理:a,b为整数,那么一定存在ax+by=gcd(a,b)ax+by的值一定是gcd(a,b)的倍数先考虑边界情况a1+b0=gcd(a,b),此时,x=1,y=0然后考虑一般情况,假设某一次得到的解是x0y0bx0+(amodb)y0=gcd(a,b)bx0+(abab)y0=gcd(a,b)ay0+b(x0bay0)=gcd(a,b)由此可得:x=y0,y=x0bay0已知任意一组解x0,y0通解为:x=x0+gcd(a,b)bnx=x0+gcd(a,b)bn
    代码:

    #include 
    #include 
    using namespace std;
    const int maxn=111111;
    int a,b,x,y;
    
    void exgcd(int a,int b,int *x,int *y)//扩展欧几里得算法
    {
        //cout<<"a="<if(b==0)
        {
            *x=1,*y=0;
            return;
        }
        exgcd(b,a%b,x,y); //r=GCD(a,b)=GCD(b, a%b)
        //cout<<"!!!a="<int t=*x;
        *x=*y;
        *y=t-a/b*(*y) ;
        
    }
    
    int main()
    {
        cin>>a>>b;
        exgcd(a,b,&x,&y);
        //cout<<"x="<while(x<0) x+=b;
        cout<<x<<endl;
    	return 0;
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
  • 相关阅读:
    Vue实现登录功能全套详解(含封装axios)
    spring ioc
    XTTS系列之三:中转空间的选择和优化
    LLM-阿里云 DashVector + ModelScope 多模态向量化实时文本搜图实战总结
    为什么别人的网页有登录拦截而你没有,这就教你学会它
    java计算机毕业设计医药垃圾分类管理系统源程序+mysql+系统+lw文档+远程调试
    Docker简介
    数字ic验证门槛高吗?
    mysql数据库简介
    innovus:报告到clock root物理距离最远的sink
  • 原文地址:https://blog.csdn.net/Rachelhello123/article/details/126087885