結果
問題 | No.1711 Divide LCM |
ユーザー | 👑 emthrm |
提出日時 | 2021-11-03 17:08:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,139 ms / 4,000 ms |
コード長 | 2,793 bytes |
コンパイル時間 | 3,240 ms |
コンパイル使用メモリ | 224,308 KB |
最終ジャッジ日時 | 2025-01-25 11:06:17 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()using ll = long long;constexpr int INF = 0x3f3f3f3f;constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;constexpr double EPS = 1e-8;constexpr int MOD = 1000000007;// constexpr int MOD = 998244353;constexpr int DY[]{1, 0, -1, 0}, DX[]{0, -1, 0, 1};constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}, DX8[]{0, -1, -1, -1, 0, 1, 1, 1};template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }struct IOSetup {IOSetup() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout << fixed << setprecision(20);}} iosetup;int pow(int n, int ex) {int tmp = n, res = 1;for (; ex > 0; ex >>= 1) {if (ex & 1) res *= tmp;tmp *= tmp;}return res;}int main() {int n; cin >> n;vector<vector<int>> p(n), e(n);map<int, int> max_e;REP(i, n) {int m; cin >> m;p[i].resize(m);e[i].resize(m);REP(j, m) {cin >> p[i][j] >> e[i][j];chmax(max_e[p[i][j]], e[i][j]);}}// for (auto [pi, ei] : max_e) cerr << pi << ' ' << ei << '\n';REP(i, n) {if (p[i].size() < max_e.size()) continue;bool is_lcm = true;REP(j, p[i].size()) is_lcm &= max_e[p[i][j]] == e[i][j];if (is_lcm) {cout << "-1\n";return 0;}}set<ll> d;REP(i, n) REP(j, 1 << p[i].size()) {int mul = 1;REP(k, p[i].size()) {if (j >> k & 1) mul *= pow(p[i][k], e[i][k]);}d.emplace(mul);}// for (ll e : d) cerr << e << ' ';// cerr << '\n';vector<pair<int, int>> max_e_v;for (auto [pi, ei] : max_e) max_e_v.emplace_back(pi, ei);vector<int> s;queue<tuple<ll, int, vector<int>>> que({{1, 0, vector<int>{}}});while (!que.empty()) {auto [mul, i, tmp_] = que.front(); que.pop();vector<int> tmp = tmp_;FOR(j, i, max_e_v.size()) {tmp.emplace_back(pow(max_e_v[j].first, max_e_v[j].second));if (d.count(mul * tmp.back()) == 0) {s = tmp;while (!que.empty()) que.pop();break;} else {que.emplace(mul * tmp.back(), j + 1, tmp);}tmp.pop_back();}}const int k = s.size();vector<vector<int>> ans(k);REP(i, n) {int a = 1;REP(j, p[i].size()) a *= pow(p[i][j], e[i][j]);REP(j, k) {if (a % s[j] > 0) {ans[j].emplace_back(a);break;}}}cout << k << '\n';REP(i, k) {cout << ans[i].size();for (int ans_j : ans[i]) cout << ' ' << ans_j;cout << '\n';}return 0;}