#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 #include #include #include #include #include #include using namespace std; using ll = long long; using Graph = vector>; #define rep(i,x) for(ll i=0;i<(ll)(x);i++) #define rrep(i,x) for(ll i=1;i<=(ll)(x);i++) #define all(v) v.begin(),v.end() #define veci vector #define vecl vector typedef pair pii; ll INF = 1e17; ll mod998 = 998244353; ll mod109 = 1e9 + 7; //vector> a(n,vector(n)); struct mint { const long long mod = mod998; long long x; mint(long long x_ = 0) : x((x_% mod + mod) % mod) {} mint& operator+=(const mint& other) { x += other.x; if (x >= mod) x -= mod; return *this; } mint& operator-=(const mint& other) { x -= other.x; if (x < 0) x += mod; return *this; } mint& operator*=(const mint& other) { x *= other.x; x %= mod; return *this; } mint& operator+=(const long long n) { return *this += mint(n); } mint& operator-=(const long long n) { return *this -= mint(n); } mint& operator*=(const long long n) { return *this *= mint(n); } mint& operator=(const mint& other) { x = other.x; return *this; } mint& operator=(const long long n) { x = n % mod; return *this; } bool operator==(const mint& other) const { return x == other.x; } bool operator!=(const mint& other) const { return x != other.x; } mint operator-() const { mint res(mod - x); return res; } mint operator+(const mint& other) const { mint res(x); return res += other; } mint operator-(const mint& other) const { mint res(x); return res -= other; } mint operator*(const mint& other) const { mint res(x); return res *= other; } mint operator+(const long long n) const { mint res(x); mint other(n); return res += other; } mint operator-(const long long n) const { mint res(x); mint other(n); return res -= other; } mint operator*(const long long n) const { mint res(x); mint other(n); return res *= other; } mint pow(long long n) const { if (n == 0) return mint(1); mint res = pow(n / 2); res *= res; if (n % 2) res *= *this; return res; } mint inv() const { return pow(mod - 2); } mint& operator/=(const mint& other) { *this *= other.inv(); return *this; } mint operator/(const mint& other) const { mint res(x); return res /= other; } }; struct combination { vector fact, ifact; combination(int m) :fact(m + 1), ifact(m + 1) { fact[0] = 1; for (int i = 1; i <= m; i++) fact[i] = fact[i - 1] * mint(i); ifact[m] = fact[m].inv(); for (int i = m; i >= 1; i--) ifact[i - 1] = ifact[i] * mint(i); } mint operator()(int n, int k) {//for n<=m, calc nck if (k < 0 || k > n) return mint(0); return fact[n] * ifact[k] * ifact[n - k]; } }; /* UnionFind:素集合系管理の構造体(union by rank) isSame(x, y): x と y が同じ集合にいるか。 計算量はならし O(α(n)) unite(x, y): x と y を同じ集合にする。計算量はならし O(α(n)) */ struct UnionFind { // The range of node number is u 0 v n-1 vector rank, parents; UnionFind() {} UnionFind(int n) { // make n trees. rank.resize(n, 0); parents.resize(n, 0); for (int i = 0; i < n; i++) { makeTree(i); } } void makeTree(int x) { parents[x] = x; // the parent of x is x rank[x] = 0; } bool isSame(int x, int y) { return findRoot(x) == findRoot(y); } void unite(int x, int y) { x = findRoot(x); y = findRoot(y); if (rank[x] > rank[y]) { parents[y] = x; } else { parents[x] = y; if (rank[x] == rank[y]) { rank[y]++; } } } int findRoot(int x) { if (x != parents[x]) parents[x] = findRoot(parents[x]); return parents[x]; } }; struct dsu { public: dsu() : _n(0) {} explicit dsu(int n) : _n(n), parent_or_size(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } std::vector> groups() { std::vector leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector& v) { return v.empty(); }), result.end()); return result; } private: int _n; // root node: -1 * component size // otherwise: parent std::vector parent_or_size; }; //DFSの基本形 /*vector seen; void dfs(const vector>& G, int v) { seen[v] = true; // v を訪問済にする // v から行ける各頂点 next_v について for (auto next_v : G[v]) { if (seen[next_v]) continue; // next_v が探索済だったらスルー dfs(G, next_v); // 再帰的に探索 } }*/ //dijkstra法 struct Edge1 { long long to; long long cost; }; using GraphE1 = vector>; using P = pair; /* dijkstra(G,s,dis) 入力:グラフ G, 開始点 s, 距離を格納する dis 計算量:O(|E|log|V|) 副作用:dis が書き換えられる */ void dijkstra(const GraphE1& G, int s, vector& dis) { priority_queue, greater

> pq; // 「仮の最短距離, 頂点」が小さい順に並ぶ dis[s] = 0; pq.emplace(dis[s], s); while (!pq.empty()) { P p = pq.top(); pq.pop(); int v = p.second; if (dis[v] < p.first) { // 最短距離で無ければ無視 continue; } for (auto& e : G[v]) { // 最短距離候補なら priority_queue に追加 if (dis[e.to] > dis[v] + e.cost) { // 最短距離候補なら priority_queue に追加 dis[e.to] = dis[v] + e.cost; pq.emplace(dis[e.to], e.to); } } } } /* Graph G(N); for (int i = 0; i < M; ++i) { int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } // BFS のためのデータ構造 vector dist(N, -1); // 全頂点を「未訪問」に初期化 queue que; // 初期条件 (頂点 0 を初期ノードとする) dist[0] = 0; que.push(0); // 0 を橙色頂点にする // BFS 開始 (キューが空になるまで探索を行う) while (!que.empty()) { int v = que.front(); // キューから先頭頂点を取り出す que.pop(); // v から辿れる頂点をすべて調べる for (int nv : G[v]) { if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない // 新たな白色頂点 nv について距離情報を更新してキューに追加する dist[nv] = dist[v] + 1; que.push(nv); } } */ void yesno(bool non) { if (non)cout << "Yes" << endl; else cout << "No" << endl; } void noyes(bool non) { if (non)cout << "No" << endl; else cout << "Yes" << endl; } long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else { return gcd(b, a % b); } } ll lcm(ll a, ll b) { return a * b / gcd(a, b); } //素数判定 bool is_prime(const unsigned n) { switch (n) { case 0: // fall-through case 1: return false; } // n > 1 が保証された // n より小さい数で n を割って余りを調べる // 素数ならば自分より小さい数(1以外)では割り切れない for (unsigned i = 2; i * i <= n; ++i) { if (n % i == 0) return false; } return true; } //mod mでaの逆元を計算. long long modinv(long long a, long long m) { long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } //素因数分解(O(√N)). vector > prime_factorize(long long N) { vector > res; for (long long a = 2; a * a <= N; ++a) { if (N % a != 0) continue; long long ex = 0; // 指数 // 割れる限り割り続ける while (N % a == 0) { ++ex; N /= a; } // その結果を push res.push_back({ a, ex }); } // 最後に残った数について if (N != 1) res.push_back({ N, 1 }); return res; } //aをbで何回割れるか(O(logN)). ll factorcnt(ll a, ll b) { ll cnt = 0; while (a % b == 0) { a = a / b; cnt++; } return cnt; } const int MOD = mod998; vector fact, fact_inv, inv; /* init_nCk :二項係数のための前処理 計算量:O(n) */ void init_nCk(int SIZE) { fact.resize(SIZE + 5); fact_inv.resize(SIZE + 5); inv.resize(SIZE + 5); fact[0] = fact[1] = 1; fact_inv[0] = fact_inv[1] = 1; inv[1] = 1; for (int i = 2; i < SIZE + 5; i++) { fact[i] = fact[i - 1] * i % MOD; inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD; fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD; } } /* nCk :MODでの二項係数を求める(前処理 int_nCk が必要) 計算量:O(1) */ long long nCk(int n, int k) { assert(!(n < k)); assert(!(n < 0 || k < 0)); return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD; } struct Edge { long long u; long long v; long long cost; }; bool comp_e(const Edge& e1, const Edge& e2) { return e1.cost < e2.cost; } // 辺を直接比較するための関数 /* Kruskal :クラスカル法で minimum spanning tree を求める構造体 入力: 辺のvector, 頂点数V 最小全域木の重みの総和: sum 計算量: O(|E|log|V|) */ struct Kruskal { UnionFind uft; long long sum; // 最小全域木の重みの総和 vector edges; int V; Kruskal(const vector& edges_, int V_) : edges(edges_), V(V_) { init(); } void init() { sort(edges.begin(), edges.end(), comp_e); // 辺の重みでソート uft = UnionFind(V); sum = 0; for (auto e : edges) { if (!uft.isSame(e.u, e.v)) { // 閉路にならなければ加える uft.unite(e.u, e.v); sum += e.cost; } } } }; //DFSの基本形 /*vector seen; void dfs(const vector>& G, int v) { seen[v] = true; // v を訪問済にする // v から行ける各頂点 next_v について for (auto next_v : G[v]) { if (seen[next_v]) continue; // next_v が探索済だったらスルー dfs(G, next_v); // 再帰的に探索 } }*/ //繰り返し二乗法 long long pow(long long a, long long n, long long m) { long long ret = 1; for (; n > 0; n >>= 1, a = a * a % m) { if (n % 2 == 1) { ret = ret * a % m; } } return ret; } //ios::sync_with_stdio(false); //std::cin.tie(nullptr); class BIT { public: BIT() = default; // 長さ size の数列で初期化 explicit BIT(size_t size) : m_bit(size + 1) {} // 数列で初期化 explicit BIT(const std::vector& v) : BIT(v.size()) { for (int i = 0; i < v.size(); ++i) { add((i + 1), v[i]); } } // 閉区間 [1, r] の合計を返す (1-based indexing) long long sum(int r) const { long long ret = 0; for (; 0 < r; r -= (r & -r)) { ret += m_bit[r]; } return ret; } // 閉区間 [l, r] の合計を返す (1-based indexing) long long sum(int l, int r) const { return (sum(r) - sum(l - 1)); } // 数列の i 番目の要素を加算 (1-based indexing) void add(int i, long long value) { for (; i < m_bit.size(); i += (i & -i)) { m_bit[i] += value; } } private: std::vector m_bit; }; int main() { int n; cin >> n; set> v; for (int x = 0; 3* x * x <= n; x++) { for (int y = x; (y + x) * (y + x) <= n + x * x; y++) { if (x == 0 && y == 0) { continue; } if ((n + x * x) % (y + x) == 0&& (n + x * x) / (y + x)-x>=y) { int z = (n + x * x) / (y + x) - x; v.insert({ x,y,z }); v.insert({ x,z,y }); v.insert({ y,x,z }); v.insert({ y,z,x }); v.insert({ z,x,y }); v.insert({ z,y,x }); } } } cout << v.size() << endl; for (tuple i : v) { cout << (get<0>(i)) <<" "<< (get<1>(i))<< " " << (get<2>(i)) << endl; } }