結果
問題 | No.2358 xy+yz+zx=N |
ユーザー |
|
提出日時 | 2023-07-08 12:57:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 6,775 bytes |
コンパイル時間 | 1,311 ms |
コンパイル使用メモリ | 138,512 KB |
最終ジャッジ日時 | 2025-02-15 08:56:30 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <complex>#include <cstdint>#include <cstring>#include <ctime>#include <deque>#include <iomanip>#include <iostream>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <unordered_map>#include <unordered_set>using namespace std;template <int mod>struct ModInt {int x;ModInt() : x(0) {}ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}ModInt &operator+=(const ModInt &p) {if ((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if ((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (int)(1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inverse();return *this;}ModInt &operator^=(long long p) { // quick_pow here:3ModInt res = 1;for (; p; p >>= 1) {if (p & 1) res *= *this;*this *= *this;}return *this = res;}ModInt operator-() const { return ModInt(-x); }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }ModInt operator^(long long p) const { return ModInt(*this) ^= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }explicit operator int() const { return x; } // added by QCFiumModInt operator=(const int p) {x = p;return ModInt(*this);} // added by QCFiumModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;while (b > 0) {t = a / b;a -= t * b;std::swap(a, b);u -= t * v;std::swap(u, v);}return ModInt(u);}friend std::ostream &operator<<(std::ostream &os, const ModInt<mod> &p) {return os << p.x;}friend std::istream &operator>>(std::istream &is, ModInt<mod> &a) {long long x;is >> x;a = ModInt<mod>(x);return (is);}};template <typename T>struct SegmentTree {using Monoid = typename T::Monoid;explicit SegmentTree(int n) : SegmentTree(std::vector<Monoid>(n, T::id())) {}explicit SegmentTree(const std::vector<Monoid> &a) : n(a.size()), sz(1) {while (sz < n) sz <<= 1;data.assign(sz << 1, T::id());std::copy(a.begin(), a.end(), data.begin() + sz);for (int i = sz - 1; i > 0; --i) {data[i] = T::merge(data[i << 1], data[(i << 1) + 1]);}}void set(int idx, const Monoid val) {idx += sz;data[idx] = val;while (idx >>= 1)data[idx] = T::merge(data[idx << 1], data[(idx << 1) + 1]);}Monoid get(int left, int right) const {Monoid res_l = T::id(), res_r = T::id();for (left += sz, right += sz; left < right; left >>= 1, right >>= 1) {if (left & 1) res_l = T::merge(res_l, data[left++]);if (right & 1) res_r = T::merge(data[--right], res_r);}return T::merge(res_l, res_r);}Monoid operator[](const int idx) const { return data[idx + sz]; }private:const int n;int sz; // sz + 原数组坐标 = 线段树里的编号,1 basedstd::vector<Monoid> data;};namespace monoid {template <typename T>struct RangeMinimumQuery {using Monoid = T;static constexpr Monoid id() { return std::numeric_limits<Monoid>::max(); }static Monoid merge(const Monoid &a, const Monoid &b) {return std::min(a, b);}};template <typename T>struct RangeMaximumQuery {using Monoid = T;static constexpr Monoid id() { return std::numeric_limits<Monoid>::lowest(); }static Monoid merge(const Monoid &a, const Monoid &b) {return std::max(a, b);}};template <typename T>struct RangeSumQuery {using Monoid = T;static constexpr Monoid id() { return 0; }static Monoid merge(const Monoid &a, const Monoid &b) { return a + b; }};} // namespace monoidtemplate <typename T>struct DSU {std::vector<T> f, siz;DSU(int n) : f(n), siz(n, 1) { std::iota(f.begin(), f.end(), 0); }T leader(T x) {while (x != f[x]) x = f[x] = f[f[x]];return x;}bool same(T x, T y) { return leader(x) == leader(y); }bool merge(T x, T y) {x = leader(x);y = leader(y);if (x == y) return false;siz[x] += siz[y];f[y] = x;return true;}T size(int x) { return siz[leader(x)]; }};std::vector<bool> prime_table(int n) {std::vector<bool> prime(n + 1, true);if (n >= 0) prime[0] = false;if (n >= 1) prime[1] = false;for (int i = 2; i * i <= n; i++) {if (!prime[i]) continue;for (int j = i * i; j <= n; j += i) {prime[j] = false;}}return prime;}std::vector<int> enumerate_primes(int n) {if (n <= 1) return {};auto d = prime_table(n);std::vector<int> primes;primes.reserve(count(begin(d), end(d), true));for (int i = 0; i < d.size(); i++) {if (d[i]) primes.push_back(i);}return primes;}void solve() {int n;std::cin >> n;std::vector<std::tuple<int, int, int>> ans;// when one is zero//for (int x = 1; x <= sqrt(n); x++) {if (n % x == 0) {ans.emplace_back(0, x, n / x);if (x != n / x) ans.emplace_back(0, n / x, x);ans.emplace_back(n / x, 0, x);if (x != n / x) ans.emplace_back(x, 0, n / x);ans.emplace_back(x, n / x, 0);if (x != n / x) ans.emplace_back(n / x, x, 0);}}// xy + yz + xz = n// n - xy = (x + y)zfor (int x = 1; x <= sqrt(n); x++) {for (int y = x; y <= sqrt(n); y++) {if ((n - x * y) % (x + y) == 0) {int z = (n - x * y) / (x + y);if (z < x or z < y) continue;// x <= y <= zans.emplace_back(x, y, z);if (x == y and x != z) {// x == y < z;ans.emplace_back(x, z, y);ans.emplace_back(z, x, y);} else if (x != y and y == z) {// x < y == zans.emplace_back(z, x, y);ans.emplace_back(z, y, x);} else if (x == y and y == z)continue;else {assert(x != y and y != z);ans.emplace_back(x, z, y);ans.emplace_back(y, x, z);ans.emplace_back(y, z, x);ans.emplace_back(z, x, y);ans.emplace_back(z, y, x);}}}}std::cout << ans.size() << '\n';for (auto &[x, y, z] : ans) std::cout << x << ' ' << y << ' ' << z << '\n';}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;while (t--) solve();return 0;}