算法基础之线性同余方程

线性同余方程

• 核心思想：

  • 转化为扩展欧几里得 求得结果d 必须为 b的因数

  •   #include<iostream>
      #include<algorithm>
      
      using namespace std;
      typedef long long LL;
      const int N = 100010;
      
      int exgcd(int a,int b,int &x,int &y)
      {
          if(!b)
          {
              x = 1 ,y = 0;
              return a;
          }
          else
          {
              int d = exgcd(b, a % b , y , x);
              y -= a/b * x;
              return d;
          }
      }
      
      int main()
      {
          int n;
          cin>>n;
      
          while(n--)
          {
              int a,b,m,x,y;
              scanf("%d %d %d", &a, &b, &m);  //输入abm 其中am 为参数
              int d = exgcd(a,m,x,y);
              if(b % d) puts("impossible");  //如果b不是d的倍数 那么无解
              else cout<<(LL) x*b/d % m<<endl;  //将x乘上系数 b/d 为了保证结果在int内要%m
          }
      }