#line 1 "No_195_\u30d5\u30a3\u30dc\u30ca\u30c3\u30c1\u6570\u5217\u306e\u7406\u89e3_2.cpp" #define YRSD // #include "YRS/aa/fast.hpp" #line 2 "YRS/all.hpp" #line 2 "YRS/aa/head.hpp" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define TE template #define TES template #define Z auto #define ep emplace_back #define eb emplace #define fi first #define se second #define all(x) (x).begin(), (x).end() #define ov(a, b, c, d, e, ...) e #define FO1(a) for (int _ = 0; _ < (a); ++_) #define FO2(i, a) for (int i = 0; i < (a); ++i) #define FO3(i, a, b) for (int i = (a); i < (b); ++i) #define FO4(i, a, b, c) for (int i = (a); i < (b); i += (c)) #define FOR(...) ov(__VA_ARGS__, FO4, FO3, FO2, FO1)(__VA_ARGS__) #define FF1(a) for (int _ = (a) - 1; _ >= 0; --_) #define FF2(i, a) for (int i = (a) - 1; i >= 0; --i) #define FF3(i, a, b) for (int i = (b) - 1; i >= (a); --i) #define FF4(i, a, b, c) for (int i = (b) - 1; i >= (a); i -= (c)) #define FOR_R(...) ov(__VA_ARGS__, FF4, FF3, FF2, FF1)(__VA_ARGS__) #define FOR_subset(t, s) for (int t = (s); t > -1; t = (t == 0 ? -1 : (t - 1) & s)) #define sort ranges::sort using namespace std; TE using vc = vector; TE using vvc = vc>; TE using T1 = tuple; TE using T2 = tuple; TE using T3 = tuple; TE using T4 = tuple; TE using max_heap = priority_queue; TE using min_heap = priority_queue, greater>; using u8 = unsigned char; using uint = unsigned int; using ll = long long; using ull = unsigned long long; using ld = long double; using i128 = __int128; using u128 = __uint128_t; using f128 = __float128; using u16 = uint16_t; using PII = pair; using PLL = pair; #ifdef YRSD constexpr bool dbg = 1; #else constexpr bool dbg = 0; #endif #line 2 "YRS/IO/IO.hpp" istream &operator>>(istream &I, i128 &x) { static string s; I >> s; int f = s[0] == '-'; x = 0; const int N = (int)s.size(); FOR(i, f, N) x = x * 10 + s[i] - '0'; if (f) x = -x; return I; } ostream &operator<<(ostream &O, i128 x) { static string s; s.clear(); bool f = x < 0; if (f) x = -x; while (x) s += '0' + x % 10, x /= 10; if (s.empty()) s += '0'; if (f) s += '-'; reverse(all(s)); return O << s; } istream &operator>>(istream &I, f128 &x) { static string s; I >> s, x = stold(s); return I; } ostream &operator<<(ostream &O, const f128 x) { return O << ld(x); } template istream &operator>>(istream &I, tuple &t) { return apply([&I](Z &...s) { ((I >> s), ...); }, t), I; } template istream &operator>>(istream &I, pair &x) { return I >> x.fi >> x.se; } template ostream &operator<<(ostream &O, const pair &x) { return O << x.fi << ' ' << x.se; } TE requires requires(T &c) { begin(c); end(c); } and (not is_same_v, string>) istream &operator>>(istream &I, T &c) { for (Z &e : c) I >> e; return I; } TE requires requires(const T &c) { begin(c); end(c); } and (not is_same_v, const char*>) and (not is_same_v, string>) and (not is_array_v> or not is_same_v>, char>) ostream &operator<<(ostream &O, const T &a) { if (a.empty()) return O; Z i = a.begin(); O << *i++; for (; i != a.end(); ++i) O << ' ' << *i; return O; } void IN() {} TE void IN(T &x, Z &...s) { cin >> x, IN(s...); } void print() { cout << '\n'; } TES void print(T &&x, S &&...y) { cout << x; if constexpr (sizeof...(S)) cout << ' '; print(forward(y)...); } void put() {} TES void put(T &&x, S &&...y) { cout << x; put(forward(y)...); } #define INT(...) int __VA_ARGS__; IN(__VA_ARGS__) #define UINT(...) uint __VA_ARGS__; IN(__VA_ARGS__) #define LL(...) ll __VA_ARGS__; IN(__VA_ARGS__) #define ULL(...) ull __VA_ARGS__; IN(__VA_ARGS__) #define I128(...) i128 __VA_ARGS__; IN(__VA_ARGS__) #define STR(...) string __VA_ARGS__; IN(__VA_ARGS__) #define CH(...) char __VA_ARGS__; IN(__VA_ARGS__) #define REAL(...) re __VA_ARGS__; IN(__VA_ARGS__) #define VEC(T, a, n) vc a(n); IN(a) void YES(bool o = 1) { print(o ? "YES" : "NO"); } void Yes(bool o = 1) { print(o ? "Yes" : "No"); } void yes(bool o = 1) { print(o ? "yes" : "no"); } void NO(bool o = 1) { YES(not o); } void No(bool o = 1) { Yes(not o); } void no(bool o = 1) { yes(not o); } void ALICE(bool o = 1) { print(o ? "ALICE" : "BOB"); } void Alice(bool o = 1) { print(o ? "Alice" : "Bob"); } void alice(bool o = 1) { print(o ? "alice" : "bob"); } void BOB(bool o = 1) { ALICE(not o); } void Bob(bool o = 1) { Alice(not o); } void bob(bool o = 1) { alice(not o); } void POSSIBLE(bool o = 1) { print(o ? "POSSIBLE" : "IMPOSSIBLE"); } void Possible(bool o = 1) { print(o ? "Possible" : "Impossible"); } void possible(bool o = 1) { print(o ? "possible" : "impossible"); } void IMPOSSIBLE(bool o = 1) { POSSIBLE(not o); } void Impossible(bool o = 1) { Possible(not o); } void impossible(bool o = 1) { possible(not o); } void TAK(bool o = 1) { print(o ? "TAK" : "NIE"); } void NIE(bool o = 1) { TAK(not o); } #line 5 "YRS/all.hpp" #if (__cplusplus >= 202002L) #include constexpr ld pi = numbers::pi_v; #endif TE constexpr T inf = numeric_limits::max(); template <> constexpr i128 inf = i128(inf) * 2'000'000'000'000'000'000; template constexpr pair inf> = {inf, inf}; TE constexpr static inline int pc(T x) { return popcount(make_unsigned_t(x)); } constexpr static inline ll len(const Z &a) { return a.size(); } void reverse(Z &a) { reverse(all(a)); } void unique(Z &a) { sort(a); a.erase(unique(all(a)), a.end()); } TE vc inverse(const vc &a) { int N = len(a); vc b(N, -1); FOR(i, N) if (a[i] != -1) b[a[i]] = i; return b; } Z QMAX(const Z &a) { return *max_element(all(a)); } Z QMIN(const Z &a) { return *min_element(all(a)); } TE Z QMAX(T l, T r) { return *max_element(l, r); } TE Z QMIN(T l, T r) { return *min_element(l, r); } constexpr bool chmax(Z &a, const Z &b) { return (a < b ? a = b, 1 : 0); } constexpr bool chmin(Z &a, const Z &b) { return (a > b ? a = b, 1 : 0); } vc argsort(const Z &a) { vc I(len(a)); iota(all(I), 0); sort(I, [&](int i, int k) { return a[i] < a[k] or (a[i] == a[k] and i < k); }); return I; } TE vc rearrange(const vc &a, const vc &I) { int N = len(I); vc b(N); FOR(i, N) b[i] = a[I[i]]; return b; } template vc pre_sum(const vc &a) { int N = len(a); vc c(N + 1); FOR(i, N) c[i + 1] = c[i] + a[i]; if (of == 0) c.erase(c.begin()); return c; } TE constexpr static int topbit(T x) { if (x == 0) return - 1; if constexpr (sizeof(T) <= 4) return 31 - __builtin_clz(x); else return 63 - __builtin_clzll(x); } TE constexpr static int lowbit(T x) { if (x == 0) return -1; if constexpr (sizeof(T) <= 4) return __builtin_ctz(x); else return __builtin_ctzll(x); } TE constexpr T floor(T x, T y) { return x / y - (x % y and (x ^ y) < 0); } TE constexpr T ceil(T x, T y) { return floor(x + y - 1, y); } TE constexpr T bmod(T x, T y) { return x - floor(x, y) * y; } TE constexpr pair divmod(T x, T y) { T q = floor(x, y); return pair{q, x - q * y}; } template T SUM(const Z &v) { return accumulate(all(v), T(0)); } int lb(const Z &a, Z x) { return lower_bound(all(a), x) - a.begin(); } TE int lb(T l, T r, Z x) { return lower_bound(l, r, x) - l; } int ub(const Z &a, Z x) { return upper_bound(all(a), x) - a.begin(); } TE int ub(T l, T r, Z x) { return upper_bound(l, r, x) - l; } template ll bina(Z f, ll l, ll r) { if constexpr (ck) assert(f(l)); while (abs(l - r) > 1) { ll x = (r + l) >> 1; (f(x) ? l : r) = x; } return l; } TE T bina_real(Z f, T l, T r, int c = 100) { while (c--) { T x = (l + r) / 2; (f(x) ? l : r) = x; } return (l + r) / 2; } Z pop(Z &s) { if constexpr (requires { s.pop_back(); }) { Z x = s.back(); return s.pop_back(), x; } else if constexpr (requires { s.top(); }) { Z x = s.top(); return s.pop(), x; } else { Z x = s.front(); return s.pop(), x; } } void setp(int x) { cout << fixed << setprecision(x); } TE inline void sh(vc &a, int N, T b = {}) { a.resize(N, b); } #line 1 "YRS/debug.hpp" #ifdef YRSD void DBG() { cerr << "]" << endl; } TES void DBG(T &&x, S &&...y) { cerr << x; if constexpr (sizeof...(S)) cerr << ", "; DBG(forward(y)...); } #define debug(...) cerr << "[" << __LINE__ << "]: [" #__VA_ARGS__ "] = [", DBG(__VA_ARGS__) void ERR() { cerr << endl; } TES void ERR(T &&x, S &&...y) { cerr << x; if constexpr (sizeof...(S)) cerr << ", "; ERR(forward(y)...); } #define err(...) cerr << "[" << __LINE__ << "]: ", ERR(__VA_ARGS__) #define asser assert #else #define debug(...) void(0721) #define err(...) void(0721) #endif #line 5 "No_195_\u30d5\u30a3\u30dc\u30ca\u30c3\u30c1\u6570\u5217\u306e\u7406\u89e3_2.cpp" // #include "YRS/IO/fast_io.hpp" // #include "YRS/random/rng.hpp" // #include "YRS/ds/basic/retsu.hpp" #line 2 "YRS/mod/binom.hpp" #line 2 "YRS/mod/mint_t.hpp" #define c constexpr template struct mint_t { using T = mint_t; static c uint m = mod; uint x; c inline uint val() const { return x; } c mint_t() : x(0) {} c mint_t(uint x) : x(x % m) {} c mint_t(ull x) : x(x % m) {} c mint_t(u128 x) : x(x % m) {} c mint_t(int x) : x((x %= mod) < 0 ? x + mod : x) {} c mint_t(ll x) : x((x %= mod) < 0 ? x + mod : x) {} c mint_t(i128 x) : x((x %= mod) < 0 ? x + mod : x) {} c T &operator+=(T p) { if ((x += p.x) >= m) x -= m; return *this; } c T &operator-=(T p) { if ((x += m - p.x) >= m) x -= m; return *this; } c T operator+(T p) const { return T(*this) += p; } c T operator-(T p) const { return T(*this) -= p; } c T &operator*=(T p) { x = ull(x) * p.x % m; return *this; } c T operator*(T p) const { return T(*this) *= p; } c T &operator/=(T p) { return *this *= p.inv(); } c T operator/(T p) const { return T(*this) /= p; } c T operator-() const { return T::gen(x ? mod - x : 0); } c T inv() const { int a = x, b = mod, x = 1, y = 0; while (b > 0) { int t = a / b; swap(a -= t * b, b); swap(x -= t * y, y); } return T(x); } c T pow(ll k) const { if (k < 0) return inv().pow(-k); T s(1), a(x); for (; k; k >>= 1, a *= a) if (k & 1) s *= a; return s; } c bool operator<(T p) const { return x < p.x; } c bool operator==(T p) const { return x == p.x; } c bool operator!=(T p) const { return x != p.x; } static c T gen(uint x) { T s; s.x = x; return s; } friend istream &operator>>(istream &cin, T &p) { ll t; cin >> t; p = t; return cin; } friend ostream &operator<<(ostream &cout, T p) { return cout << p.x; } static c int get_mod() { return mod; } static c PII ntt_info() { if (mod == 167772161) return {25, 17}; if (mod == 469762049) return {26, 30}; if (mod == 754974721) return {24, 362}; if (mod == 998244353) return {23, 31}; if (mod == 120586241) return {20, 74066978}; if (mod == 880803841) return {23, 211}; if (mod == 943718401) return {22, 663003469}; if (mod == 1004535809) return {21, 582313106}; if (mod == 1012924417) return {21, 368093570}; return {-1, -1}; } static c bool can_ntt() { return ntt_info().fi != -1; } }; #undef c using M99 = mint_t<998244353>; using M17 = mint_t<1000000007>; #ifdef FIO template void rd(mint_t &x) { LL(y); x = y; } template void wt(mint_t x) { wt(x.x); } #endif #line 4 "YRS/mod/binom.hpp" TE struct binom { const int p = T::get_mod(); vc fa{1, 1}, ifa{1, 1}, in{0, 1}; T inv(int n) { assert(0 <= n); while (len(in) <= n) { int k = len(in); int q = (p + k - 1) / k; int r = k * q - p; in.ep(in[r] * T(q)); } return in[n]; } T fac(int n) { if (n >= p) return 0; while (len(fa) <= n) { int k = len(fa); fa.ep(fa[k - 1] * T(k)); } return fa[n]; } T ifac(int n) { if (n < 0) return T(0); while (len(ifa) <= n) ifa.ep(ifa.back() * inv(len(ifa))); return ifa[n]; } T C(int N, int K) { assert(N >= 0); if (K < 0 or N < K) return 0; return fac(N) * ifac(K) * ifac(N - K); } T lucas(ll N, ll K) { if (K > N) return 0; if (K == 0) return 1; return C(N % p, K % p) * lucas(N / p, K / p); } T C_naive(ll N, ll K) { assert(N >= 0); if (K < 0 or N < K) return 0; chmin(K, N - K); T x = 1; FOR(i, K) x *= (N - i); return x * ifac(K); } }; #line 2 "YRS/line/solve_line.hpp" // 无解返回空 // 一组解返回解 // 多解返回解+解空间基底 TE vc> solve_line(vc> A, vc B, int N = -1, int M = -1) { if (N == -1) { N = len(A); assert(N > 0); M = len(A[0]); } assert(N == len(A) and N == len(B)); int rk = 0; FOR(j, M) { if (rk == N) break; FOR(i, rk, N) if (A[i][j] != 0) { swap(A[rk], A[i]); swap(B[rk], B[i]); break; } if (A[rk][j] == 0) continue; T c = T(1) / A[rk][j]; for (Z &&x : A[rk]) x *= c; B[rk] *= c; FOR(i, N) if (i != rk) { T c = A[i][j]; if (c == T(0)) continue; B[i] -= B[rk] * c; FOR(k, j, M) { A[i][k] -= A[rk][k] * c; } } ++rk; } FOR(i, rk, N) if (B[i] != 0) return {}; vc> res(1, vc(M)); vc pv(M, -1); int p = 0; FOR(i, rk) { while (A[i][p] == 0) ++p; res[0][p] = B[i]; pv[p] = i; } FOR(j, M) if (pv[j] == -1) { vc x(M); x[j] = -1; FOR(k, j) if (pv[k] != -1) x[k] = A[pv[k]][j]; res.ep(x); } return res; } #line 10 "No_195_\u30d5\u30a3\u30dc\u30ca\u30c3\u30c1\u6570\u5217\u306e\u7406\u89e3_2.cpp" using mint = M99; void Yorisou() { LL(a, b, c); constexpr int N = 50; vc f(N), g(N); f[0] = 1; g[1] = 1; FOR(i, 2, N) f[i] = f[i - 1] + f[i - 2], g[i] = g[i - 1] + g[i - 2]; PLL ans = inf; FOR(i, N) FOR(k, N) FOR(j, N) { vc> A(3); A[0] = {f[i], g[i]}; A[1] = {f[k], g[k]}; A[2] = {f[j], g[j]}; FOR(i, 3) FOR(k, 2) A[i][k] = A[i][k].x; vc B{a, b, c}; Z r = solve_line(A, B); if (r.empty()) continue; Z ck = [&](ll aa, ll bb) -> bool { if (min(aa, bb) == 0) return 0; if (aa * f[i] + bb * g[i] != a) return 0; if (aa * f[k] + bb * g[k] != b) return 0; if (aa * f[j] + bb * g[j] != c) return 0; return 1; }; ll aa = r[0][0].val(), bb = r[0][1].val(); if (ck(aa, bb)) chmin(ans, PLL{aa, bb}); } if (a == b and a == c) { FOR(i, 50) if (max(f[i], g[i]) <= a) { ll t = a - f[i]; if (g[i] == 0) { if (t == 0) chmin(ans, PLL{1, 1}); } else if (t % g[i] == 0) { chmin(ans, PLL {1, t / g[i]}); } } } if (ans == inf) print(-1); else print(ans); } constexpr int tests = 0, fl = 0, DB = 10; #line 1 "YRS/aa/main.hpp" int main() { cin.tie(0)->sync_with_stdio(0); int T = 1; if (fl) cerr.tie(0); if (tests and not fl) IN(T); for (int i = 0; i < T or fl; ++i) { Yorisou(); if (fl and i % DB == 0) cerr << "Case: " << i << '\n'; } return 0; } #line 55 "No_195_\u30d5\u30a3\u30dc\u30ca\u30c3\u30c1\u6570\u5217\u306e\u7406\u89e3_2.cpp"