最小生成树、质因数分解

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e3;
int a[N][N];
int d[N];
bitset<N> intree;
void solve() {
  int n, m;
  cin >> n >> m;
  memset(a, 0x3f, sizeof a);
  memset(d, 0x3f, sizeof d);
  for (int i = 1; i <= n; i++) a[i][i] = 0;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    a[u][v] = min(a[u][v], w);
    a[v][u] = min(a[v][u], w);
  }
  int ans = 0;
  d[1] = 0;
  for (int i = 1; i <= n; i++) {
    int u = 1;
    for (int j = 1; j <= n; j++) {
      if (intree[u] || (!intree[j] && d[j] < d[u])) {
        u = j;
      }
      ans += d[u];
      intree[u] = true;
      d[u] = 0;
      for (int j = 1; j <= n; j++) {
        if (intree[j]) continue;
        d[j] = min(d[j], a[u][j]);
      }
    }
  }
  cout << ans;
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 9;

struct Edge {  //生成结构体用于村粗出点和价值
  int x, w;
  bool operator<(const Edge &u) const { return w == u.w ? x < u.x : w > u.w; }
};  //重载运算符以使用堆存储
vector<Edge> g[N];
int d[N];
bitset<N> intree;  //标记
void solve() {
  int n, m;
  cin >> n >> m;
  memset(d, 0x3f, sizeof d);
  for (int i = 1; i <= n; i++) g[i].push_back({i, 0});  //自身调用
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].push_back({v, w});  //取小,可以认为是双向的
    g[v].push_back({u, w});
  }
  int ans = 0;
  priority_queue<Edge> pq;  //优先队列
  pq.push({1, 0});
  d[1] = 0;
  while (pq.size()) {        //常规判断条件
    auto [x, w] = pq.top();  //有点像序对
    pq.pop();
    if (intree[x]) continue;  //如果使用过则跳过此点
    intree[x] = true;         //设当前点为使用
    ans += w;
    d[x] = 0;
    for (auto &[y, w] : g[x]) {  //找下一个点
      if (!intree[y] && w < d[y]) {
        d[y] = w;
        pq.push({y, w});
      }
    }
  }
  for (int i = 1; i <= n; i++) {  //如果存在独立点,则不存在最小生成树
    if (!intree[i]) {
      ans = -1;
    }
  }
  cout << ans;
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 9;

struct Edge {
  int u, v, w;
  bool operator<(const Edge &m) const { return w < m.w; }
};

int d[N];
int pre[N];

int find(int x) { return pre[x] = (pre[x] == x ? x : find(pre[x])); }

void solve() {
  int n, m;
  cin >> n >> m;
  memset(d, 0x3f, sizeof d);

  vector<Edge> es;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    es.push_back({u, v, w});
  }
  sort(begin(es), end(es));
  int ans = 0;
  for (int i = 1; i <= n; i++) pre[i] = i;
  for (auto &[u, v, w] : es) {
    if (find(u) == find(v)) continue;
    ans += w;
    pre[find(u)] = find(v);
  }
  for (int i = 1; i < n; i++)
    if (find(i) != find(i + 1)) ans = -1;

  cout << ans;
}

signed main() {
  int _ = 1;
  while (_--) solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
void solve() {
  int n;
  cin >> n;
  vector<int> res;
  for (int i = 1; i <= n / i; i++) {
    if (n % i == 0) {
      res.push_back(i);
      res.push_back(n / i);
    }
  }
  sort(res.begin(), res.end());
  res.erase(unique(res.begin(), res.end()), res.end());
  for (auto& i : res) {
    cout << i << " ";
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}

// Problem: ${json.name}
// Contest: ${json.group}
// URL: ${json.url}
// Memory Limit: ${json.memoryLimit} MB
// Time Limit: ${json.timeLimit} ms
// More thought is needed

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 9;
void solve() {
  int n;
  cin >> n;
  vector<int> res;
  for (int i = 2; i <= n / i; i++) {
    if (n % i) {
      continue;
    }
    res.push_back(i);
    while (n % i == 0) {
      n /= i;
    }
  }
  if (n > 1) res.push_back(n);
  sort(res.begin(), res.end());
  for (auto& i : res) {
    cout << i << " ";
  }
}

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  solve();
  return 0;
}