結果

問題 No.1917 LCMST
ユーザー rhoo
提出日時 2025-07-16 09:56:33
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 6,277 bytes
コンパイル時間 15,915 ms
コンパイル使用メモリ 397,840 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-16 09:57:14
合計ジャッジ時間 25,694 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_imports,non_snake_case,dead_code)]
use std::{cmp::Reverse as Rev,ops::Range,collections::*,iter::*};
use proconio::{marker::*,*};



// LCMST



#[fastout]
fn main(){
    input!{
        n:usize,
        a:[usize;n],
    }

    let divs=(0..n).map(|i|divisor(a[i])).collect::<Vec<_>>();
    let mut it=0;
    let mut div_to_id=HashMap::new();
    let mut id_to_div=vec![];

    for i in 0..n{
        for &d in &divs[i]{
            if !div_to_id.contains_key(&d){
                div_to_id.insert(d,it);
                id_to_div.push(d);
                it+=1;
            }
        }
    }

    let mut div_set=vec![vec![];id_to_div.len()];
    for i in 0..n{
        for &d in &divs[i]{
            let id=div_to_id[&d];
            div_set[id].push(a[i]);
        }
    }

    type MultiSet=BTreeMap<usize,usize>;
    fn add(set:&mut MultiSet,a:usize){
        *set.entry(a).or_insert(0)+=1;
    }
    #[track_caller]
    fn rem(set:&mut MultiSet,a:usize){
        let e=set.get_mut(&a).unwrap();
        *e-=1;
        if *e==0{
            set.remove(&a);
        }
    }

    #[derive(Clone,Debug)]
    struct Queue{
        d:usize,
        que:MultiSet,
        co_que:MultiSet,
        w:usize,
    }

    let init_que=|d:usize|{
        let mut co_que=MultiSet::new();
        let id=div_to_id[&d];
        for &d in &div_set[id]{
            add(&mut co_que,d);
        }
        Queue{
            d,
            que:MultiSet::new(),
            co_que,
            w:!0,
        }
    };
    
    let mut que=id_to_div.iter().map(|&d|init_que(d)).collect::<Vec<Queue>>();
    let mut min=BTreeSet::new();
    
    cap!{
        #![&a:[usize],&mut que:[Queue],&divs:[Vec<usize>],&div_to_id:HashMap<usize,usize>,&mut min:BTreeSet<(usize,usize)>]
        
        // a[i]をprimとして確定させる
        fn mov(i:usize){
            for &n in &divs[i]{
                let id=div_to_id[&n];
                let que=&mut que[id];
                if que.w!=!0{
                    min.remove(&(que.w,que.d));
                }
                
                add(&mut que.que,a[i]);
                rem(&mut que.co_que,a[i]);
                
                if !que.que.is_empty() && !que.co_que.is_empty(){
                    let m0=que.que.first_key_value().unwrap().0;
                    let m1=que.co_que.first_key_value().unwrap().0;
                    que.w=m0/que.d*m1;
                    min.insert((que.w,que.d));
                } else{
                    que.w=!0;
                }
            }
        }
    }
    
    let mut index=HashMap::new();
    for i in 0..n{
        index.entry(a[i]).or_insert(vec![]).push(i);
    }
    
    mov!(0);
    let mut ans=0;
    for _ in 1..n{
        let (w,d)=min.first().unwrap();
        ans+=w;
        let id=div_to_id[&d];
        let new=*que[id].co_que.first_key_value().unwrap().0;
        let idx=index.get_mut(&new).unwrap().pop().unwrap();
        mov!(idx);
    }
    
    println!("{ans}");
}



// 約数列挙
// 小さい順になってる
// 0はpanic
fn divisor(n:usize)->Vec<usize>{
    assert!(n!=0);
    let mut ret=vec![1];
    for i in 2..{
        if i*i>n{
            break;
        }
        if n%i==0{
            ret.push(i);
        }
    }
    for i in (0..ret.len()).rev(){
        if ret[i]*ret[i]!=n{
            ret.push(n/ret[i]);
        }
    }
    ret
}



#[macro_export]
macro_rules! cap{
    ()=>{};
    (#![] $($fn:tt)*)=>{
        cap!([],[],[],[],[$($fn)*],[],[]);
    };
    (#![$($g:tt)*] $($fn:tt)*)=>{
        cap!([$($g)*,],[],[],[],[$($fn)*],[],[]);
    };
    ([$name:ident:$t:ty,$($rem:tt)*],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$($fn:tt)*],[],[])=>{
        cap!([$($rem)*],[$name:$t,$($ga)*],[$name,$($gn)*],[$name,$($ge)*],[$($fn)*],[],[]);
    };
    ([$($flag:tt)? $name:ident:$t:ty,$($rem:tt)*],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$($fn:tt)*],[],[])=>{
        cap!([$($rem)*],[$name:$($flag)?$t,$($ga)*],[$name,$($gn)*],[$($flag)?$name,$($ge)*],[$($fn)*],[],[]);
    };
    ([&mut $name:ident:$t:ty,$($rem:tt)*],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$($fn:tt)*],[],[])=>{
        cap!([$($rem)*],[$name:&mut $t,$($ga)*],[$name,$($gn)*],[&mut $name,$($ge)*],[$($fn)*],[],[]);
    };
    ([],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$(#[$($att:tt)*])? fn $name:ident($($arg:tt)*) $body:block $($rem:tt)*],[$($info:tt)*],[$($fn:tt)*])=>{
        cap!([],[$($ga)*],[$($gn)*],[$($ge)*],[$($rem)*],[(($(#[$($att)*])?),$name,($($arg)*),(),$body),$($info)*],[$name,$($fn)*]);
    };
    ([],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[$(#[$($att:tt)*])? fn $name:ident($($arg:tt)*)->$ret:ty $body:block $($rem:tt)*],[$($info:tt)*],[$($fn:tt)*])=>{
        cap!([],[$($ga)*],[$($gn)*],[$($ge)*],[$($rem)*],[(($(#[$($att)*])?),$name,($($arg)*),$ret,$body),$($info)*],[$name,$($fn)*]);
    };
    ([],[$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[],[$($info:tt)*],[$($fn:tt)*])=>{
        cap!(@make_fn [$($ga)*],[$($gn)*],[$($ge)*],[$($info)*],[$($fn)*]);
    };
    (@make_fn [$($ga:ident:$gt:ty,)*],[$($gn:tt)*],[$($ge:tt)*],[(($($att:tt)*),$name:ident,($($arg:tt)*),$ret:ty,$body:block),$($rem:tt)*],[$($fn:tt)*])=>{
        $($att)*
        fn $name($($ga:$gt,)*$($arg)*)->$ret{
            $(#[allow(unused_variables)] let $ga=$ga;)*
            cap!(@make_macros ($),[$($gn)*],[$($fn)*]);
            $body
        }
        cap!(@make_fn [$($ga:$gt,)*],[$($gn)*],[$($ge)*],[$($rem)*],[$($fn)*]);
    };
    (@make_fn [$($ga:tt)*],[$($gn:tt)*],[$($ge:tt)*],[],[$($fn:tt)*])=>{
        cap!(@make_global_macros ($),[$($ge)*],[$($fn)*]);
    };
    (@make_macros ($dol:tt),[$($gn:ident,)*],[$name:ident,$($rem:tt)*])=>{
        #[allow(unused_macros)]
        macro_rules! $name{
            ($dol($dol arg:expr),*)=>{$name($($gn,)* $dol($dol arg),*)}
        }
        cap!(@make_macros ($),[$($gn,)*],[$($rem)*]);
    };
    (@make_macros ($dol:tt),[$($gn:ident,)*],[])=>{};
    (@make_global_macros ($dol:tt),[$($ge:expr,)*],[$name:ident,$($rem:tt)*])=>{
        #[allow(unused_macros)]
        macro_rules! $name{
            ($dol($dol arg:expr),*)=>{$name($($ge,)* $dol($dol arg),*)}
        }
        cap!(@make_global_macros ($),[$($ge,)*],[$($rem)*]);
    };
    (@make_global_macros ($dol:tt),[$($ge:expr,)*],[])=>{};
}
0