Submission #1513445

---

Source Code Expand

#include <bits/stdc++.h>

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
typedef std::vector<long> LI;
typedef std::queue<long> QI;
#define rep(i,n) for(long i = 0; i < (long)n; ++i)
const double pi = M_PI;
const long mod = 1000000007;

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }
template<> void scan1(long& x) { if( scanf("%ld", &x) < 0 ) exit(0); }
template<> void scan1(std::string& x) { if( not ( std::cin >> x ) ) exit(0); }
template<> void scan1(LI& xs) { for(long &x : xs) scan1(x); }
void scan() {}
template<typename Head, typename... Tail>
void scan(Head& x, Tail&... xs) {
  scan1(x); scan(xs...);
}

long gcd(long x, long y) {
   return y == 0 ? x : gcd(y, x%y);
}

struct Solver {
   Solver() { fprintf(stderr, "--------Solver begin--------\n"); }
   ~Solver() { fprintf(stderr, "--------Solver end--------\n"); }
   void solve() {
      long x, y;
      if( scanf("%ld/%ld", &x, &y) < 0 ) exit(0);
      long lower = floor(2.0 * x / y);
      long upper = floor(2.0 * x / y + 2 - 1);
      // long lower = (2 * x + (y - 1)) / y - 1;
      // long upper = (2 * (x + y)) / y - 1;
      bool exist = false;
      if( lower > 2000000000 ) {
         puts("Impossible");
         return;
      }
      for(long n = lower; n <= upper; ++n) {
         if( n < 1 ) continue;
         bool cond = gcd(n, y) * gcd(x, y) % y == 0;
         if( not cond ) continue;
         long ma = n * (y * ((n + 1)) - 2 * (x));
         long mb = 2 * y;
         long m = ma / mb;
         if( ma % mb != 0 ) continue;
         if( not ( 1 <= m and m <= n ) ) continue;
         printf("%ld %ld\n", n, m);
         exist = true;
      }
      if( not exist ) {
         puts("Impossible");
      }
   }
};

int main() {
   loop std::unique_ptr<Solver>(new Solver())->solve();
}

Submission Info

Judge Result