結果
問題 | No.1711 Divide LCM |
ユーザー | 👑 emthrm |
提出日時 | 2021-11-03 16:59:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,778 bytes |
コンパイル時間 | 3,340 ms |
コンパイル使用メモリ | 224,052 KB |
最終ジャッジ日時 | 2025-01-25 11:03:37 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 WA * 7 |
ソースコード
#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(); } 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; }