#line 1 "playspace/main.cpp" #include #line 8 "library/gandalfr/other/io_supporter.hpp" template std::ostream &operator<<(std::ostream &os, const std::vector &v) { for (int i = 0; i < (int)v.size(); i++) os << v[i] << (i + 1 != (int)v.size() ? " " : ""); return os; } template std::ostream &operator<<(std::ostream &os, const std::set &st) { for (const T &x : st) { std::cout << x << " "; } return os; } template std::ostream &operator<<(std::ostream &os, const std::multiset &st) { for (const T &x : st) { std::cout << x << " "; } return os; } template std::ostream &operator<<(std::ostream &os, const std::deque &dq) { for (const T &x : dq) { std::cout << x << " "; } return os; } template std::ostream &operator<<(std::ostream &os, const std::pair &p) { os << p.first << ' ' << p.second; return os; } template std::ostream &operator<<(std::ostream &os, std::queue &q) { int sz = q.size(); while (--sz) { os << q.front() << ' '; q.push(q.front()); q.pop(); } os << q.front(); q.push(q.front()); q.pop(); return os; } template std::istream &operator>>(std::istream &is, std::vector &v) { for (T &in : v) is >> in; return is; } template std::istream &operator>>(std::istream &is, std::pair &p) { is >> p.first >> p.second; return is; } #line 4 "library/gandalfr/math/prime_number_utility.hpp" #line 6 "library/gandalfr/math/prime_number_utility.hpp" #line 6 "library/gandalfr/math/enumeration_utility.hpp" #line 5 "library/gandalfr/standard/mod_integer.hpp" inline long long mod_inverse(long long a, int mod) { assert(mod > 0); long long b = mod, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, std::swap(a, b); u -= t * v, std::swap(u, v); } u %= mod; if (u < 0) u += mod; return u; } // mod_integer

a := Pを法とするときの整数型; template class mod_integer { private: long long val; // 値は必ず 0 <= val < mod に保たれる friend mod_integer operator+(const mod_integer &a) { return a; } friend mod_integer operator-(const mod_integer &a) { return -a.val; } friend mod_integer operator+(const mod_integer &a, const mod_integer &b) { return mod_integer(a.val + b.val); } friend mod_integer operator-(const mod_integer &a, const mod_integer &b) { return mod_integer(a.val - b.val); } friend mod_integer operator*(const mod_integer &a, const mod_integer &b) { return mod_integer(a.val * b.val); } friend mod_integer operator/(const mod_integer &a, const mod_integer &b) { return mod_integer((a.val * mod_inverse(b.val, mod)) % mod); } friend bool operator==(const mod_integer &a, const mod_integer &b) { return a.val == b.val; } friend bool operator!=(const mod_integer &a, const mod_integer &b) { return a.val != b.val; } // map とかに乗せたいので、便宜的に定義 friend bool operator<(const mod_integer &a, const mod_integer &b) { return a.val < b.val; } public: mod_integer(long long n) : val(n) { val %= mod; if (val < 0) val += mod; } mod_integer() : val(0) {} int value() const { return (int)val; } mod_integer &operator=(const mod_integer &a) = default; mod_integer &operator+=(const mod_integer &a) { val += a.val; if (val >= mod) val -= mod; return *this; } mod_integer &operator-=(const mod_integer &a) { val -= a.val; if (val < 0) val += mod; return *this; } mod_integer &operator*=(const mod_integer &a) { (val *= a.val) %= mod; return *this; } mod_integer &operator/=(const mod_integer &a) { (val *= mod_inverse(a.val, mod)) %= mod; return *this; } friend std::istream &operator>>(std::istream &is, mod_integer &a) { is >> a.val; a.val %= mod; if (a.val < 0) a.val += mod; return is; } friend std::ostream &operator<<(std::ostream &os, const mod_integer &a) { os << a.val; return os; } }; // d_mod_integer

a := Pを法とするときの整数型; template class dynamic_mod_integer { private: using d_mod_integer = dynamic_mod_integer; static inline int mod = 998244353; long long val; // 値は必ず 0 <= val < mod に保たれる friend d_mod_integer operator+(const d_mod_integer &a) { return a; } friend d_mod_integer operator-(const d_mod_integer &a) { return -a.val; } friend d_mod_integer operator+(const d_mod_integer &a, const d_mod_integer &b) { return d_mod_integer(a.val + b.val); } friend d_mod_integer operator-(const d_mod_integer &a, const d_mod_integer &b) { return d_mod_integer(a.val - b.val); } friend d_mod_integer operator*(const d_mod_integer &a, const d_mod_integer &b) { return d_mod_integer(a.val * b.val); } friend d_mod_integer operator/(const d_mod_integer &a, const d_mod_integer &b) { return d_mod_integer((a.val * mod_inverse(b.val, mod)) % mod); } friend bool operator==(const d_mod_integer &a, const d_mod_integer &b) { return a.val == b.val; } friend bool operator!=(const d_mod_integer &a, const d_mod_integer &b) { return a.val != b.val; } // map とかに乗せたいので、便宜的に定義 friend bool operator<(const d_mod_integer &a, const d_mod_integer &b) { return a.val < b.val; } public: dynamic_mod_integer(long long n) : val(n) { val %= mod; if (val < 0) val += mod; } dynamic_mod_integer() : val(0) {} int value() const { return (int)val; } static void set_mod(int _mod) { assert(_mod >= 0); mod = _mod; } d_mod_integer &operator=(const d_mod_integer &a) = default; d_mod_integer &operator+=(const d_mod_integer &a) { val += a.val; if (val >= mod) val -= mod; return *this; } d_mod_integer &operator-=(const d_mod_integer &a) { val -= a.val; if (val < 0) val += mod; return *this; } d_mod_integer &operator*=(const d_mod_integer &a) { (val *= a.val) %= mod; return *this; } d_mod_integer &operator/=(const d_mod_integer &a) { (val *= mod_inverse(a.val, mod)) %= mod; return *this; } friend std::istream &operator>>(std::istream &is, d_mod_integer &a) { is >> a.val; a.val %= mod; if (a.val < 0) a.val += mod; return is; } friend std::ostream &operator<<(std::ostream &os, const d_mod_integer &a) { os << a.val; return os; } }; using mint = mod_integer<1000000007>; using _mint = mod_integer<998244353>; using dmint = dynamic_mod_integer<-1>; #line 8 "library/gandalfr/math/enumeration_utility.hpp" template T power(T x, long long n) { T ret = static_cast(1); while (n > 0) { if (n & 1) ret = ret * x; x = x * x; n >>= 1; } return ret; } long long power(long long x, long long n) { long long ret = 1; while (n > 0) { if (n & 1) ret = ret * x; x = x * x; n >>= 1; } return ret; } long long power(long long x, long long n, int MOD) { long long ret = 1; x %= MOD; while (n > 0) { if (n & 1) ret = ret * x % MOD; x = x * x % MOD; n >>= 1; } return ret; } long long power(long long x, long long n, long long MOD) { long long ret = 1; x %= MOD; while (n > 0) { if (n & 1) ret = (__int128_t)ret * x % MOD; x = (__int128_t)x * x % MOD; n >>= 1; } return ret; } template class factorial { private: static inline std::vector fact{T(1)}; public: factorial() = delete; ~factorial() = delete; static T get(int n) { while (n >= fact.size()) fact.push_back(fact.back() * fact.size()); return fact[n]; } }; mint (*fact)(int) = factorial::get; _mint (*_fact)(int) = factorial<_mint>::get; template T permutation(int n, int k) { assert(0 <= k && k <= n); return factorial::get(n) / factorial::get(n - k); } mint (*perm)(int, int) = permutation; _mint (*_perm)(int, int) = permutation<_mint>; template static T combnation(int n, int k) { assert(0 <= k && k <= n); return factorial::get(n) / (factorial::get(k) * factorial::get(n - k)); } mint (*comb)(int, int) = combnation; _mint (*_comb)(int, int) = combnation<_mint>; #line 8 "library/gandalfr/math/prime_number_utility.hpp" /** * @see https://drken1215.hatenablog.com/entry/2023/05/23/233000 */ bool MillerRabin(long long N, const std::vector &A) { long long s = 0, d = N - 1; while (d % 2 == 0) { ++s; d >>= 1; } for (auto a : A) { if (N <= a) return true; long long t, x = power(a, d, N); if (x != 1) { for (t = 0; t < s; ++t) { if (x == N - 1) break; x = (__int128_t)x * x % N; } if (t == s) return false; } } return true; } /** * @brief 素数判定や列挙をサポートするクラス * @brief 素数篩を固定サイズで構築、それをもとに素数列挙などを行う */ class Eratosthenes { protected: static inline int seive_size = (1 << 24); static inline std::vector sieve; static inline std::vector primes{2, 3}, movius, min_factor; static void make_table() { sieve.assign(seive_size, true); sieve[0] = sieve[1] = false; movius.assign(seive_size, 1); min_factor.assign(seive_size, 1); for (int i = 2; i <= seive_size; ++i) { if (!sieve[i]) continue; movius[i] = -1; min_factor[i] = i; primes.push_back(i); for (int j = i * 2; j < seive_size; j += i) { sieve[j] = false; movius[j] = ((j / i) % i == 0 ? 0 : -movius[j]); if (min_factor[j] == 1) min_factor[j] = i; } } } static std::vector> fast_factorize(long long n) { std::vector> ret; while (n > 1) { if (ret.empty() || ret.back().first != min_factor[n]) { ret.push_back({min_factor[n], 1}); } else { ret.back().second++; } n /= min_factor[n]; } return ret; } static std::vector> naive_factorize(long long n) { std::vector> ret; for (long long p : primes) { if (n == 1 || p * p > n) break; while (n % p == 0) { if (ret.empty() || ret.back().first != p) ret.push_back({p, 1}); else ret.back().second++; n /= p; } } if (n != 1) ret.push_back({n, 1}); return ret; } public: Eratosthenes() = delete; ~Eratosthenes() = delete; static void set_init_size(int size) { assert(sieve.empty()); seive_size = size; } /** * @brief n が素数かを判定 * @attention if n < (1 << 24) : O(1) * @attention else : O(log(N)) */ static bool is_prime(long long n) { if (sieve.empty()) make_table(); assert(1 <= n); if (n > 2 && (n & 1LL) == 0) { return false; } else if (n < seive_size) { return sieve[n]; } else if (n < 4759123141LL) { return MillerRabin(n, {2, 7, 61}); } else { return MillerRabin( n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022}); } } /** * @brief 素因数分解する * @return factorize(p1^e1 * p2^e2 * ...) => {{p1, e1}, {p2, e2], ...}, * @return factorize(1) => {} * @attention if n < (1 << 24) : O(log(N)) * @attention if n < (1 << 24) : O(N^(3/2)) */ static std::vector> factorize(long long n) { if (sieve.empty()) make_table(); assert(1 <= n); if (n < seive_size) { return fast_factorize(n); } else { return naive_factorize(n); } } static int Movius(int n) { if (movius.empty()) make_table(); assert(1 <= n); return movius.at(n); } /** * @brief オイラーのトーシェント関数 */ long long totient(long long n) { long long ret = 1; for (auto [b, e] : factorize(n)) ret *= power(b, e - 1) * (b - 1); return ret; } static int kth_prime(int k) { return primes.at(k); } }; #line 4 "playspace/main.cpp" using namespace std; using ll = long long; const int INF = 1001001001; const int MAXINT = std::numeric_limits::max(); const int MININT = std::numeric_limits::min(); const ll INFLL = 1001001001001001001; const ll MAXLL = std::numeric_limits::max(); const ll MINLL = std::numeric_limits::min(); const ll MOD = 1000000007; const ll _MOD = 998244353; #define rep(i, j, n) for(ll i = (ll)(j); i < (ll)(n); i++) #define rrep(i, j, n) for(ll i = (ll)(n-1); i >= (ll)(j); i--) #define all(a) (a).begin(),(a).end() #define LF cout << endl #ifdef ENABLE_MULTI_FOR #define mrep(it, mr) for(multi_iter it(mr); !it.fin(); ++it) #endif template inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } void Yes(bool ok){ std::cout << (ok ? "Yes" : "No") << std::endl; } int main(void){ ll N; cin >> N; ll cu = N; vector ans{N}; string str; int cnt = 0; while(cu > 1) { if (cu % 2 == 0) { ans.push_back(cu / 2); cu >>= 1; str += '/'; } else { if (cnt < 500) { ans.push_back(cu * 3 - 1); cu = cu * 3 - 1; str += '-'; } else { ans.push_back(cu * 3 + 1); cu = cu * 3 + 1; str += '+'; } } cnt++; } cout << ans.size()-1 << endl; cout << str << endl; }