算法基础之表达整数的奇怪方式

表达整数的奇怪方式

中国剩余定理:

• 求M = 所有m之积 然后M_i = M / m_i

  • x = 如下图 满足要求
    • 

扩展中国剩余定理

• 

• 找到x **使得x mod m_i = a_i**成立

  • 对于每两个式子 都可以推出①式

    • 即 用扩展欧几里得算法 可以算出k1,-k2和m2–m1

    • 

    • 判无解 : 若**(m2–m1) % d != 0** 说明该等式无解 即原方程无解 本题无解

  • 找到最小正整数解

    • 已知k1的通式(如下图 代入原方程可证成立) 则求最小正整数解 只要 %abs(a2/d)
    • 

  • 等效替代

    • 设a₀ = gcd(a₁,a₂) , m₀ = k₁ * a₁ + m₁ 得到新的式子和原方程长得一模一样

    • 

    • 也就是说 每两个式子 都可以通过合并的方式 写成一个式子

    • 只要将所有n个式子全都合并成一个式子 x = k*a + m 就可以求解x了

•   #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    LL exgcd(LL a,LL b,LL &x,LL &y){  //拓展欧几里得算法
        if(!b){
            x=1,y=0;
            return a;
        }
    
        LL d=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return d;
    }
    
    int main()
    {
        int n;
        cin>>n;
        LL x=0,m1,a1;
        cin>>a1>>m1;
        for(int i=0;i<n-1;i++){  //输入n-1次
            LL m2,a2;
            cin>>a2>>m2;
            LL k1,k2;
            LL d=exgcd(a1, a2,k1,k2);
            if((m2-m1) % d)  //无解
            {
                x = -1;
                break;
            }
            
            k1 *= (m2-m1) / d;  //k1乘相应系数
            k1 = (k1 %(a2/d) + a2 / d) % (a2/d);  //见下方注释
            
            x = k1 * a1 + m1;  //根据公式③
            //更新a1 m1 进行下一次合并
            m1 = k1 * a1 + m1;
            a1 = abs(a1 * a2 /d);
        }
    
        if(x!=-1) x=(m1%a1+a1)%a1;  //若x为负数 将x变成正数
    
        cout<<x<<endl;
        return 0;
    }
  

  • k1 = (k1 %(a2/d) + a2 / d) % (a2/d);
    • c++中 若k1为负数 %完 仍然是负数 而不是正数 因此 我们在%完后 +上一个膜数 再膜一次
    • 就可以求出最小正整数k1

参考题解 ：https://www.acwing.com/solution/content/3539/