結果

問題 No.1711 Divide LCM
ユーザー chineristAC
提出日時 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言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
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
      |              ^~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#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]);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0