Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define fi first
- #define se second
- #define mp make_pair
- #define pb push_back
- #define pii pair<int, int>
- #define INF 200000001
- #define EPS 1e-9
- typedef long long ll;
- typedef complex<double> cd;
- const ll mod = 1e9+7;
- const double pi = acos(-1);
- int n,i,j,k,t;
- ll inverse(ll val, ll mod){
- if(val == 1)
- return 1;
- ll ans = (-mod/val*inverse(mod%val, mod))%mod;
- if(ans<0)
- ans += mod;
- return ans;
- }
- int main(){
- ll n,m,k,a;
- while(scanf("%lld %lld %lld %lld", &n, &m, &k, &a), n||m||k||a){
- ll b = a+k-n;
- if(a == 0 || m == 0){
- if(a==m){
- if(b)
- puts("Impossible");
- else
- printf("%lld\n", n);
- }
- else if(a==0){
- if(k>=n&&(k-n)%m==0)
- printf("%lld\n", k);
- else
- puts("Impossible");
- }
- else{
- if(k+a<=n&&(n-k-a)%a==0)
- printf("%lld\n", n);
- else
- puts("Impossible");
- }
- }
- else if(b % __gcd(a, m)){
- puts("Impossible");
- }
- else{
- ll e=0,f;
- if(b < 0){
- b = - b;
- ll tmp = b / a + (b%a>0);
- e += tmp;
- }
- ll d = b%m;
- bool ada = true;
- if(d > 0){
- f = __gcd(d, a);
- d /= f;
- if(__gcd(a/f, m) == 1){
- ll g = inverse((a/f)%m, m);
- ll wew = (-d*g)%m;
- e += (wew + m)%m;
- }
- else
- ada = false;
- }
- if(ada)
- printf("%lld\n", e * a + a + k);
- else
- puts("Impossible");
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement