#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #include #include #include #include namespace fastio { #ifndef FAST_IO #define FAST_IO #endif struct Pre { char num[10000][4]; constexpr Pre() : num() { for (int i = 0; i < 10000; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i][j] = n % 10 | '0'; n /= 10; } } } } constexpr pre; static constexpr int BUF_SZ = 1 << 18; char *ibuf, obuf[BUF_SZ], outs[100]; int outi, obufi; void __attribute__((constructor)) _c() { struct stat sb; fstat(0, &sb); ibuf = (char *)mmap(0, sb.st_size, PROT_READ, MAP_SHARED /*| MAP_POPULATE*/, 0, 0); } void flush() { write(1, obuf, obufi), obufi = 0; } void input(char &c) { c = *ibuf++; } void input(string &x) { x.clear(); char c; do { input(c); } while (isspace(c)); do { x += c, input(c); } while (!isspace(c)); } template void input_integer(T &x) { char c; do { input(c); } while (c < '-'); bool minus = 0; if constexpr (is_signed::value || is_same_v) { if (c == '-') { minus = 1, input(c); } } x = 0; while (c >= '0') { x = x * 10 + (c & 15), input(c); } if constexpr (is_signed::value || is_same_v) { if (minus) { x = -x; } } } template void input_real(T &x) { string s; input(s); x = stod(s); } void input(int &x) { input_integer(x); } void input(long long &x) { input_integer(x); } void input(__int128 &x) { input_integer(x); } void input(uint32_t &x) { input_integer(x); } void input(uint64_t &x) { input_integer(x); } void input(unsigned __int128 &x) { input_integer(x); } void input(double &x) { input_real(x); } template void input(vector &x) { for (auto &d : x) input(d); } template void input(array &x) { for (auto &d : x) input(d); } template void input(pair &p) { input(p.first), input(p.second); } template void input_tuple(T &t) { if constexpr (N < std::tuple_size::value) { auto &x = std::get(t); input(x); input_tuple(t); } } template void input(tuple &tpl) { input_tuple(tpl); } void in() {} template void in(H &h, T &... t) { input(h), in(t...); } void output(const char c) { if (obufi == BUF_SZ) flush(); obuf[obufi++] = c; } void output(const string &s) { for (char c : s) output(c); } template void output_integer(T x) { if (obufi > BUF_SZ - 100) flush(); if (x < 0) { obuf[obufi++] = '-', x = -x; } for (outi = 96; x >= 10000; outi -= 4) { memcpy(outs + outi, pre.num[x % 10000], 4); x /= 10000; } if (x >= 1000) { memcpy(obuf + obufi, pre.num[x], 4); obufi += 4; } else if (x >= 100) { memcpy(obuf + obufi, pre.num[x] + 1, 3); obufi += 3; } else if(x >= 10) { int q = (x * 103) >> 10; obuf[obufi] = q | '0'; obuf[obufi + 1] = (x - q * 10) | '0'; obufi += 2; } else { obuf[obufi++] = x | '0'; } memcpy(obuf + obufi, outs + outi + 4, 96 - outi); obufi += 96 - outi; } template void output_real(T x) { ostringstream oss; oss << fixed << setprecision(15) << double(x); string s = oss.str(); output(s); } void output(int x) { output_integer(x); } void output(long long x) { output_integer(x); } void output(__int128 x) { output_integer(x); } void output(uint32_t x) { output_integer(x); } void output(uint64_t x) { output_integer(x); } void output(unsigned __int128 x) { output_integer(x); } void output(double x) { output_real(x); } void output(long double x) { output_real(x); } template void output(const vector &val) { size_t n = val.size(); for (size_t i = 0; i < n; i++) { if (i) output(' '); output(val[i]); } } template void output(const pair &val) { output(val.first); output(' '); output(val.second); } template void output_tuple(const T &t) { if constexpr (N < std::tuple_size::value) { if constexpr (N > 0) { output(' '); } const auto x = std::get(t); output(x); output_tuple(t); } } template void output(tuple &tpl) { output_tuple(tpl); } template void output(const array &val) { size_t n = val.size(); for (size_t i = 0; i < n; i++) { if (i) output(' '); output(val[i]); } } void out() { output('\n'); } template void out(H &&h, T &&... t) { output(h); if (sizeof...(T)) output(sep); out(t...); } void outr() {} template void outr(H &&h, T &&... t) { output(h); outr(t...); } void __attribute__((destructor)) _d() { flush(); } } // namespace fastio using fastio::in; using fastio::out; #define SHOW(x) static_cast(0) using ll = long long; using D = double; using LD = long double; using P = pair; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using i128 = __int128; using u128 = unsigned __int128; using vi = vector; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; template using vvvvc = vector>; template using vvvvvc = vector>; #define vv(type, name, h, ...) \ vector> name(h, vector(__VA_ARGS__)) #define vvv(type, name, h, w, ...) \ vector>> name( \ h, vector>(w, vector(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector>>> name( \ a, vector>>( \ b, vector>(c, vector(__VA_ARGS__)))) template using PQ = priority_queue>; template using minPQ = priority_queue, greater>; #define rep1(a) for(ll i = 0; i < a; i++) #define rep2(i, a) for(ll i = 0; i < a; i++) #define rep3(i, a, b) for(ll i = a; i < b; i++) #define rep4(i, a, b, c) for(ll i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep1(a) for(ll i = (a)-1; i >= 0; i--) #define rrep2(i, a) for(ll i = (a)-1; i >= 0; i--) #define rrep3(i, a, b) for(ll i = (b)-1; i >= a; i--) #define rrep4(i, a, b, c) for(ll i = (b)-1; i >= a; i -= c) #define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__) #define for_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s))) #define ALL(v) v.begin(), v.end() #define RALL(v) v.rbegin(), v.rend() #define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) #define SZ(v) ll(v.size()) #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define LB(c, x) distance((c).begin(), lower_bound(ALL(c), (x))) #define UB(c, x) distance((c).begin(), upper_bound(ALL(c), (x))) template T SUM(const vector &v) { T res = 0; for(auto &&a : v) res += a; return res; } template vector> RLE(const vector &v) { if (v.empty()) return {}; T cur = v.front(); int cnt = 1; vector> res; for (int i = 1; i < (int)v.size(); i++) { if (cur == v[i]) cnt++; else { res.emplace_back(cur, cnt); cnt = 1; cur = v[i]; } } res.emplace_back(cur, cnt); return res; } template inline bool chmax(T &a, const S &b) { return (a < b ? a = b, true : false); } template inline bool chmin(T &a, const S &b) { return (a > b ? a = b, true : false); } void YESNO(bool flag) { out(flag ? "YES" : "NO"); } void yesno(bool flag) { out(flag ? "Yes" : "No"); } int popcnt(int x) { return __builtin_popcount(x); } int popcnt(u32 x) { return __builtin_popcount(x); } int popcnt(ll x) { return __builtin_popcountll(x); } int popcnt(u64 x) { return __builtin_popcountll(x); } int popcnt_sgn(int x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(ll x) { return (__builtin_parityl(x) & 1 ? -1 : 1); } int popcnt_sgn(u64 x) { return (__builtin_parityl(x) & 1 ? -1 : 1); } int highbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int highbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int highbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int highbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } template T get_bit(T x, int k) { return x >> k & 1; } template T set_bit(T x, int k) { return x | T(1) << k; } template T reset_bit(T x, int k) { return x & ~(T(1) << k); } template T flip_bit(T x, int k) { return x ^ T(1) << k; } template T popf(deque &que) { T a = que.front(); que.pop_front(); return a; } template T popb(deque &que) { T a = que.back(); que.pop_back(); return a; } template T pop(queue &que) { T a = que.front(); que.pop(); return a; } template T pop(stack &que) { T a = que.top(); que.pop(); return a; } template T pop(PQ &que) { T a = que.top(); que.pop(); return a; } template T pop(minPQ &que) { T a = que.top(); que.pop(); return a; } template i128 binary_search(F check, i128 ok, i128 ng, bool check_ok = true) { if (check_ok) assert(check(ok)); while (ng - ok > 1) { i128 mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; } template double binary_search_real(F check, double ok, double ng, int iter = 60) { for (int _ = 0; _ < iter; _++) { double mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return (ok + ng) / 2; } // max x s.t. b*x <= a ll div_floor(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b - (a % b < 0); } // max x s.t. b*x < a ll div_under(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b - (a % b <= 0); } // min x s.t. b*x >= a ll div_ceil(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b + (a % b > 0); } // min x s.t. b*x > a ll div_over(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b + (a % b >= 0); } // x = a mod b (b > 0), 0 <= x < b ll modulo(ll a, ll b) { assert(b > 0); ll c = a % b; return c < 0 ? c + b : c; } // (q,r) s.t. a = b*q + r, 0 <= r < b (b > 0) // div_floor(a,b), modulo(a,b) pair divmod(ll a, ll b) { ll q = div_floor(a,b); return {q, a - b*q}; } const vc witness{2,3,5,7,11,13,17,19,23,29,31,37,41}; // mod < 2^{80} i128 mul(i128 a, i128 b, i128 mod) { array ar{}, br{}; rep(i,3) ar[i] = (a>>(30*i)) & ((1<<30)-1); rep(i,3) br[i] = (b>>(30*i)) & ((1<<30)-1); i128 ans = ar[2]*br[2]; ans = ((ans << 30) + ar[2]*br[1] + ar[1]*br[2]) % mod; ans = ((ans << 30) + ar[0]*br[2] + ar[1]*br[1] + ar[2]*br[0]) % mod; ans = ((ans << 30) + ar[0]*br[1] + ar[1]*br[0]) % mod; return ((ans << 30) + ar[0]*br[0]) % mod; } i128 pow_mod(i128 ai, i128 d, i128 mod) { i128 ret = 1; i128 p = witness[ai]; int x = 0; while(d){ if(d&1) ret = mul(ret, p, mod); p = mul(p, p, mod); d >>= 1; x++; } return ret; } int trz(i128 x){ static constexpr u64 msk = (u64)0-1; u64 h = x>>64, l = (u128)x&(u128)msk; if(l == 0) return countr_zero(h) + 64; return countr_zero(l); } i128 bgcd(i128 x, i128 y) { if(x == 0 or y == 0) return x + y; int n = trz(x), m = trz(y); x >>= n, y >>= m; while(x != y){ if(x > y) x = (x-y) >> trz(x-y); else y = (y-x) >> trz(y-x); } return x << min(n,m); } bool miller_rabin(i128 n) { int s = 0, t; i128 d = n - 1; while (d % 2 == 0) d >>= 1, s++; rep(i,13){ i128 a = witness[i]; if (n <= a) return true; i128 x = pow_mod(i, d, n); if (x != 1) { for (t = 0; t < s; t++) { if (x == n-1) break; x = mul(x, x, n); } if (t == s) return false; } } return true; } i128 pollard_rho(i128 n) { if (n % 2 == 0) return 2; i128 c = 1; while(true) { auto f = [&] (i128 x) { return (mul(x,x,n)+c)%n; }; i128 x = c, y = f(x); while (true) { i128 g = bgcd(y-x+n, n); if(g == 0 or g == n) break; if(g != 1){ if (miller_rabin(g)) return g; else if (miller_rabin(n / g)) return n / g; else return pollard_rho(g); } x = f(x); y = f(f(y)); } c++; } } vector> factorize(i128 n) { vector> res; while (n > 1 and !miller_rabin(n)) { i128 p = pollard_rho(n); int e = 0; while (n % p == 0) { n /= p; e++; } res.emplace_back(p, e); } if (n > 1) res.emplace_back(n, 1); return res; } vector divisor(i128 n) { vector res{1}; const auto pf = factorize(n); for (const auto& [p, e] : pf) { int s = res.size(); for (int i = 0; i < s; i++) { i128 m = 1; for (int _ = 0; _ < e; _++) { m *= p; res.push_back(res[i]*m); } } } return res; } i128 n = 0; vc> ans1, ans2, ans3; constexpr i128 INF = (i128)1 << 80; i128 sat_pow(i128 a, i128 e){ i128 ret = 1; rep(_,e){ if(ret >= (INF+a-1)/a) return INF; ret *= a; if(ret >= INF) return INF; } return ret; } void fix_e(int e){ i128 s = 0; i128 r = 1; i128 llim = 1; while(sat_pow(llim, e) <= n) llim++; vc pw(llim); rep(i,1,llim) pw[i] = sat_pow(i,e); rep(l,1,llim){ while(r < llim and s+pw[r] <= n) s += pw[r++]; if(s == n) ans3.emplace_back(e,l,r-1); s -= pw[l]; } } vc divs; void e1(){ divs = divisor(2*n); for(auto d : divs) { i128 x = d, y = n*2/d; if((x&1) != (y&1) and x <= y) ans1.emplace_back(1, (y-x+1)/2, (y+x-1)/2); } } void e2(){ auto check = [&] (i128 len) { i128 l = binary_search([&](i128 x){ return (x+len-1)*(x+len)*((x+len)*2-1) - (x-1)*x*(2*x-1) <= 6*n; }, 1, (i128)1000000000010, false); if((l+len-1)*(l+len)*((l+len)*2-1) - (l-1)*l*(2*l-1) == 6*n) ans2.emplace_back(2, l, l+len-1); }; divs = divisor(6*n); for(auto d : divs) { if(d > 200000000) continue; check(d); } } void e3(){ i128 s = 0; i128 r = 1; for(i128 l = 1; l <= 100000000; l++){ while(s+r*r*r <= n) s += r*r*r, r++; if(s == n) ans3.emplace_back(3,l,r-1); s -= l*l*l; } } void solve() { string ns; in(ns); for(char c : ns) n = n * 10 + c-'0'; e1(); e2(); e3(); rep(e,4,80) fix_e(e); out(SZ(ans1) + SZ(ans2) + SZ(ans3)); sort(ALL(ans1)); sort(ALL(ans2)); for (auto x : ans1) out(x); for (auto x : ans2) out(x); for (auto x : ans3) out(x); } int main() { int tc = 1; // in(tc); while(tc--){ solve(); } }