#include #include #include #include #include using namespace std; int64_t extgcd(int64_t a, int64_t b, int64_t &x, int64_t &y) { for (int64_t u = y = 1, v = x = 0; a; ) { int64_t q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; } vector fib; // ひとつの場合はextgcdより良い感じになるものを探す void solve_single(int64_t X) { int64_t A = X; int64_t B = X; for(size_t i = 0; i < fib.size() - 1; i++) { int64_t x, y, kmax, kmin; extgcd(fib[i], fib[i + 1], x, y); // fib[i]x + fib[i + 1]y = 1 x *= X; y *= X; // x - k*fib[i + 1] >= 1, y + k*fib[i] >= 1の条件下xを最小化、yを最小化 if(x > 0) { // kを大きくする // x - 1 >= k * fib[i + 1] kmax = (x - 1) / fib[i + 1]; } else { // kを小さくする // 1 - x <= -k * fib[i + 1] kmax = -((1 - x + fib[i + 1] - 1) / fib[i + 1]); } int64_t a = (x - kmax * fib[i + 1]), b = (y + kmax * fib[i]); if(a >= 1 && b >= 1) { if(A > a || (A == a && B >= b)) { A = a; B = b; } } } cout << A << " " << B <= 1) { int64_t cur = tB - tA; tB = A; tA = cur; if(tA < A || (tA == A && tB <= B)) { A = tA; B = tB; } } } bool check(int64_t bX, int64_t X, int64_t Y) { int64_t cur; while(bX <= Y) { if(bX == Y || X == Y) return true; cur = bX + X; bX = X; X = cur; } return false; } void solve(int64_t X, int64_t Y, int64_t Z) { int64_t A = numeric_limits::max(); int64_t B = numeric_limits::max(); vector tmp = {X, Y, Z}; sort(tmp.begin(), tmp.end()); X = tmp[0]; Y = tmp[1]; Z = tmp[2]; // Zに関するループ for(size_t k = 0; k < fib.size() - 1; k++) { // X * fib[k] + nX * fib[k + 1] = Z int64_t nX = Z - X * fib[k]; if(nX <= 0) break; if(nX % fib[k + 1] != 0) continue; nX /= fib[k + 1]; if(check(X, nX, Y)) { long a, b; back(X, nX, a, b); if(a < A || (a == A && b < B)) { A = a; B = b; } } } if(A == numeric_limits::max()) { cout << -1 << endl; }else{ cout << A << " " << B << endl; } } int main() { fib.push_back(0); fib.push_back(1); for(size_t i = 2; fib[i - 2] <= 1000000000; i++) { fib.push_back(fib[i - 2] + fib[i - 1]); } int64_t X, Y, Z; cin >> X >> Y >> Z; if(X == Y && Y == Z) { solve_single(X); } else { solve(X, Y, Z); } }