和有理数取余区别在哪?为什么过程完全不一样?
查看原帖
和有理数取余区别在哪?为什么过程完全不一样?
696758
15Hb楼主2023/1/10 15:48

写出不定方程后,不就是得到一个同余方程吗,为什么不能按照有理数取余来做呢?

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
LL gcd(LL a, LL b){
   return b == 0? a :gcd(b, a%b);
}
pair<LL , LL> exgcd(LL a, LL b){
   if(b == 0) return {1, 0};
   auto [x, y] = exgcd(b , a % b);
   return {y, x - y* (a / b)};
}
int main(){
   LL x, y, m, n, L, b, a;
   cin >>x >>y >>m >>n >>L;
   b = m - n, a = y - x;
   if( b < 0){
      b = -b;
      a = -a;
   }
   a %= L, b %= L;
   if(  a%gcd(b, L)!=1 ) cout<<"Impossible\n";
   //题目转化为 求解同余方程   bx = a (mod L)
   //先找出x1(逆元)  bx1 = 1 (mod L) 左右两边*a,得到 x = a*x1 (mod L)
   auto [x1, y1] = exgcd(b, L);
   x1 = (x1 % L + L)% L; //得到b在模L下的逆元
   cout<< ((a * x1) % L + L)% L; //
   return 0;
}

2023/1/10 15:48
加载中...