模线性同余方程组的求解
1 #include <cstdio> 2 #include <cstring> 3 4 using namespace std; 5 const int N = 1005; 6 7 #define ll long long 8 ll a[N] , b[N]; 9 10 ll ex_gcd(ll a , ll &x , ll b , ll &y) 11 { 12 if(b == 0){ 13 x = 1 , y = 0; 14 return a; 15 } 16 ll ans = ex_gcd(b , x , a%b , y); 17 ll t = x; 18 x= y , y = t - (a/b)*y; 19 return ans; 20 } 21 22 ll mod_line(int n) 23 { 24 ll r = b[0] , lcm = a[0] , x , y; 25 for(int i = 1 ; i<n ; i++) 26 { 27 ll del = b[i] - r; 28 ll g = ex_gcd(lcm , x , a[i] , y); 29 if(del % g != 0) return -1; 30 ll Mod = a[i] / g; 31 x = ((x*del/g % Mod) + Mod)%Mod; 32 r = r + lcm*x; 33 lcm = lcm*a[i]/g; 34 r %= lcm; 35 } 36 return r; 37 } 38 39 int main() 40 { 41 // freopen("a.in" , "r" , stdin); 42 int n; 43 while(scanf("%d" , &n) == 1) 44 { 45 for(int i= 0 ; i<n ; i++) 46 scanf("%I64d%I64d" , a+i , b+i); 47 printf("%I64d\n" , mod_line(n)); 48 } 49 return 0; 50 }