#include "prime/osak.hpp"
#pragma once #include "factor-enumerate.hpp" template <int MAX> vector<int> osak(int n) { static vector<int> f = factor_enumerate(MAX); vector<int> ret; while (f[n]) ret.push_back(f[n]), n /= f[n]; return ret; } template <int MAX> vector<pair<int, int>> osak_table(int n) { static vector<int> f = factor_enumerate(MAX); vector<pair<int, int>> v; for (; f[n]; n /= f[n]) { if (v.empty() || v.back().first != f[n]) { v.emplace_back(f[n], 1); } else { v.back().second++; } } return v; } template <int MAX> vector<int> osak_divisors(int n) { if(n == 0) return {}; if(n == 1) return vector<int>(1, 1); auto p = osak_table<MAX>(n); vector<int> ds; auto dfs = [&](auto r, int i, int c) { if (i == (int)p.size()) { ds.push_back(c); return; } for (int j = 0; j <= p[i].second; j++) { r(r, i + 1, c); c *= p[i].first; } }; dfs(dfs, 0, 1); sort(begin(ds), end(ds)); return ds; }
#line 2 "prime/osak.hpp" #line 2 "prime/factor-enumerate.hpp" vector<int> factor_enumerate(int N) { vector<int> lp(N + 1, 0); if (N < 2) return lp; vector<int> pr{2, 3}; for (int i = 2; i <= N; i += 2) lp[i] = 2; for (int i = 3; i <= N; i += 6) lp[i] = 3; for (int i = 5, d = 4; i <= N; i += d = 6 - d) { if (lp[i] == 0) { lp[i] = i; pr.push_back(i); } for (int j = 2; j < (int)pr.size() && i * pr[j] <= N; ++j) { lp[i * pr[j]] = pr[j]; if (pr[j] == lp[i]) break; } } return lp; } #line 4 "prime/osak.hpp" template <int MAX> vector<int> osak(int n) { static vector<int> f = factor_enumerate(MAX); vector<int> ret; while (f[n]) ret.push_back(f[n]), n /= f[n]; return ret; } template <int MAX> vector<pair<int, int>> osak_table(int n) { static vector<int> f = factor_enumerate(MAX); vector<pair<int, int>> v; for (; f[n]; n /= f[n]) { if (v.empty() || v.back().first != f[n]) { v.emplace_back(f[n], 1); } else { v.back().second++; } } return v; } template <int MAX> vector<int> osak_divisors(int n) { if(n == 0) return {}; if(n == 1) return vector<int>(1, 1); auto p = osak_table<MAX>(n); vector<int> ds; auto dfs = [&](auto r, int i, int c) { if (i == (int)p.size()) { ds.push_back(c); return; } for (int j = 0; j <= p[i].second; j++) { r(r, i + 1, c); c *= p[i].first; } }; dfs(dfs, 0, 1); sort(begin(ds), end(ds)); return ds; }