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

2023-12-22 23:33:00

表达整数的奇怪方式

中国剩余定理:

  • 求M = 所有m之积 然后Mi = M / mi在这里插入图片描述

    • x = 如下图 满足要求
      • 在这里插入图片描述

扩展中国剩余定理

  • 在这里插入图片描述

  • 找到x **使得x mod mi = ai**成立

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

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

      • 在这里插入图片描述

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

    • 找到最小正整数解

      • 已知k1的通式(如下图 代入原方程可证成立) 则求最小正整数解 只要 %abs(a2/d)
      • 在这里插入图片描述
    • 等效替代

      • 设a0 = gcd(a1,a2) , m0 = k1 * a1 + m1 得到新的式子和原方程长得一模一样

      • 在这里插入图片描述

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

      • 只要将所有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/

文章来源:https://blog.csdn.net/Pisasama/article/details/135162429
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。