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

表达整数的奇怪方式

中国剩余定理:

• 求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/