daily pastebin goal
16%
SHARE
TWEET

Untitled

a guest Jun 13th, 2018 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fi first
  6. #define se second
  7. #define mp make_pair
  8. #define pb push_back
  9. #define pii pair<int, int>
  10. #define INF 200000001
  11. #define EPS 1e-9
  12.  
  13. typedef long long ll;
  14. typedef complex<double> cd;
  15.  
  16. const ll mod = 1e9+7;
  17. const double pi = acos(-1);
  18.  
  19. int n,i,j,k,t;
  20.  
  21. ll inverse(ll val, ll mod){
  22.     if(val == 1)
  23.         return 1;
  24.     ll ans = (-mod/val*inverse(mod%val, mod))%mod;
  25.     if(ans<0)
  26.         ans += mod;
  27.     return ans;
  28. }
  29.  
  30. int main(){
  31.     ll n,m,k,a;
  32.     while(scanf("%lld %lld %lld %lld", &n, &m, &k, &a), n||m||k||a){
  33.         ll b = a+k-n;
  34.         if(a == 0 || m == 0){
  35.             if(a==m){
  36.                 if(b)
  37.                     puts("Impossible");
  38.                 else
  39.                     printf("%lld\n", n);
  40.             }
  41.             else if(a==0){
  42.                 if(k>=n&&(k-n)%m==0)
  43.                     printf("%lld\n", k);
  44.                 else
  45.                     puts("Impossible");
  46.             }
  47.             else{
  48.                 if(k+a<=n&&(n-k-a)%a==0)
  49.                     printf("%lld\n", n);
  50.                 else
  51.                     puts("Impossible");
  52.             }
  53.         }
  54.         else if(b % __gcd(a, m)){
  55.             puts("Impossible");
  56.         }
  57.         else{
  58.             ll e=0,f;
  59.             if(b < 0){
  60.                 b = - b;
  61.                 ll tmp = b / a + (b%a>0);
  62.                 e += tmp;
  63.             }
  64.             ll d = b%m;
  65.             bool ada = true;
  66.             if(d > 0){
  67.                 f = __gcd(d, a);
  68.                 d /= f;
  69.                 if(__gcd(a/f, m) == 1){
  70.                     ll g = inverse((a/f)%m, m);
  71.                     ll wew = (-d*g)%m;
  72.                     e += (wew + m)%m;
  73.                 }
  74.                 else
  75.                     ada = false;
  76.             }
  77.             if(ada)
  78.                 printf("%lld\n", e * a + a + k);
  79.             else
  80.                 puts("Impossible");
  81.         }
  82.     }
  83.     return 0;
  84. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top