Quick actions

cmd+k|ctrl+k

Navigation

Languages

EEA_01

Snippet info

Language

Cpp

Visibility

public

Author

karthik.pasupulatei

Created

2021-07-06T14:21:05.020379Z

Updated

2021-07-06T15:47:27.565198Z

#include "bits/stdc++.h"
using namespace std ; 

void EEA(int a , int b , int &x , int &y ){
     if(b==0){
          x =1 , y= 0 ; return ;
     }
     int x1  , y1 ; 
     EEA(b ,a%b , x1 ,y1); 
     x = y1 ; 
     y = x1 - y1*(a/b); 
}
string solve(int n , int m , int a ,int k){
     // 3 5           2   2 
     // n+m + m + m = k +  a + a 
     // n-k = ax + m(-y)
     // 1 =      +5()
     
     //3x - 5y = 1
     //2    1
     if(abs(n-k)%(__gcd(m,a)))return "Impossible" ;
     
     int x , y ;
     if(n > k ) m = -m  ; 
     else a = -a; 
     EEA(max(a,m) ,min(a,m),x,y); 
     
     cout << a  << " " << m  << '\n' ; 
     a = abs(a) ; m = abs(m);
     cout << x <<" " << y <<"\n"  ; 
      cout << a  << " " << m  << '\n' ; 
     return to_string(a*abs(x)+ k) ;   
     
}
int main(){
     while(true){
          int n , m , a , k ;
          cin >> n >> m >> a >>  k ; 
          if((n|m|a|k) == 0)break;
          cout << solve(n,m,a,k) <<"\n" ;
 
     }
     return 0 ;
}
INFO