結果
問題 | No.1711 Divide LCM |
ユーザー |
|
提出日時 | 2021-08-07 21:31:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,730 bytes |
コンパイル時間 | 3,139 ms |
コンパイル使用メモリ | 202,692 KB |
最終ジャッジ日時 | 2025-01-23 16:49:29 |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
In file included from /usr/include/c++/13/string:43, from /usr/include/c++/13/bits/locale_classes.h:40, from /usr/include/c++/13/bits/ios_base.h:41, from /usr/include/c++/13/ios:44, from /usr/include/c++/13/ostream:40, from /usr/include/c++/13/iostream:41, from main.cpp:5: /usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<char, std::allocator<char> >::_Vector_impl::~_Vector_impl()’: /usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = char]’: target specific option mismatch 184 | ~allocator() _GLIBCXX_NOTHROW { } | ^ In file included from /usr/include/c++/13/vector:66, from main.cpp:6: /usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here 133 | struct _Vector_impl | ^~~~~~~~~~~~
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <iostream>#include <vector>#include <string>#include <map>#include <set>#include <queue>#include <algorithm>#include <cmath>#include <iomanip>#include <random>#include <stdio.h>#include <fstream>#include <functional>#include <cassert>#include "testlib.h"using namespace std;#define rep(i,n,c) for (int i=0;i<n;i+=c)#define append push_back#define all(x) (x).begin(), (x).end()template<class T>using vec = vector<T>;template<class T>using vvec = vec<vec<T>>;template<class T>using vvvec = vec<vvec<T>>;using ll = long long;using pii = pair<int,int>;using pll = pair<ll,ll>;template<class T>bool chmin(T &a, T b){if (a>b){a = b;return true;}return false;}template<class T>bool chmax(T &a, T b){if (a<b){a = b;return true;}return false;}template<class T>T sum(vec<T> x){T res=0;for (auto e:x){res += e;}return res;}template<class T>void printv(vec<T> x){for (auto e:x){cout<<e<<" ";}cout<<"\n";}const int M = 1000000000;int spf[32000];void calc_spf(){spf[1] = 1;for (int i=2;i<32000;i++){if (spf[i]==0){spf[i] = i;for (int j=2*i;j<32000;j+=i){spf[j] = i;}}}}vec<int> prime = {};void make_prime(){calc_spf();for (int i=2;i<32000;i++){if (spf[i]==i){prime.append(i);}}}vec<pll> factorization(ll n){assert (1 <= n);assert (n <= M);vec<pll> res;ll cnt = 0;for (auto p:prime){cnt = 0;while (n%p==0){cnt += 1;n /= p;}if (cnt!=0){res.append({p,cnt});}}if (n!=1){res.append({n,1});}return res;}vec<ll> divisors(vec<pll> n_prime){vec<ll> res = {1ll};ll tmp;for (auto [p,cnt]:n_prime){vec<ll> new_res;for (auto d:res){tmp = d;for (int i=0;i<cnt+1;i++){new_res.append(tmp);tmp *= p;}}res = new_res;}return res;}ll pow(ll n,ll k){ll res = 1;while (k){if (k&1){res *= n;}n *= n;k >>= 1;}return res;}int main(int argc, char* argv[]){registerValidation(argc,argv);ios::sync_with_stdio(false);std::cin.tie(nullptr);make_prime();int N;N = inf.readInt(1,2000);inf.readEoln();vec<ll> A(N);map<ll,ll> lcm_A;set<ll> all_divisors;set<ll> check;for (int i=0;i<N;i++){A[i] = inf.readLong(1ll,1000000000ll);check.insert(A[i]);auto a_prime = factorization(A[i]);for (auto [p,cnt]:a_prime){lcm_A[p];chmax(lcm_A[p],cnt);}auto D = divisors(a_prime);for (auto d:D){all_divisors.insert(d);}if (i==N-1){inf.readEoln();}else{inf.readSpace();}}inf.readEof();assert (check.size()==N);vec<ll> P(0);for (auto [p,cnt]:lcm_A){P.append(pow(p,cnt));}int n = P.size();deque<pll> deq = {{1,-1}};ll prod = -1;while (!deq.empty()){auto [v,k] = deq.front();deq.pop_front();for (int i=k+1;i<n;i++){if (!all_divisors.count(v*P[i])){prod = v*P[i];deq = {};break;}deq.append({v*P[i],i});}}if (prod==-1){cout<<-1<<endl;return 0;}vec<ll> selected_P(0);for (auto p:P){if (prod%p==0){selected_P.append(p);}}int k = selected_P.size();vec<vec<ll>> S(k,vec<ll>(0));for (auto a:A){for (int i=0;i<k;i++){if (a%selected_P[i]){S[i].append(a);break;}}}cout<<k<<endl;for (int i=0;i<k;i++){cout<<S[i].size()<<" ";printv(S[i]);}}