結果

問題 No.2718 Best Consonance
ユーザー 37kt37kt
提出日時 2024-12-17 10:09:08
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 1,715 ms / 4,000 ms
コード長 11,693 bytes
コンパイル時間 14,721 ms
コンパイル使用メモリ 384,952 KB
実行使用メモリ 10,240 KB
最終ジャッジ日時 2024-12-17 10:09:40
合計ジャッジ時間 30,433 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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

pub use __cargo_equip::prelude::*;
use chminmax::{chmax, chmin};
use fast_factorize::divisors;
#[allow(unused_imports)]
use proconio::{
input,
marker::{Bytes, Chars, Usize1},
};
const INF: usize = 1 << 60;
fn main() {
input! {
n: usize,
mut ab: [(usize, usize); n],
}
ab.sort_by_key(|&(a, b)| !(a * b));
let mut f = vec![INF; 200_001];
let mut res = 0;
for &(a, b) in &ab {
for x in divisors(a) {
chmax!(res, b * x / f[x]);
chmin!(f[x], a);
}
}
println!("{}", res);
}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
/// - `algebraic 0.1.0 (path+███████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate
    ::__cargo_equip::crates::algebraic`
/// - `chminmax 0.1.0 (path+███████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate
    ::__cargo_equip::crates::chminmax`
/// - `fast-factorize 0.1.0 (path+███████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate
    ::__cargo_equip::crates::fast_factorize`
/// - `montgomery-modint 0.1.0 (path+██████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate
    ::__cargo_equip::crates::montgomery_modint`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod algebraic {pub use crate::__cargo_equip::macros::algebraic::*;pub trait Algebra{type S;}pub trait Act:Algebra{type X;fn act(f:&Self::S
            ,x:&Self::X)->Self::X;}pub trait Monoid:Algebra{fn e()->Self::S;fn op(x:&Self::S,y:&Self::S)->Self::S;}pub trait Group:Monoid{fn inv(x
            :&Self::S)->Self::S;}pub trait Zero{fn zero()->Self;fn is_zero(&self)->bool;}pub trait One{fn one()->Self;fn is_one(&self)->bool
            ;}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_algebra{($ident:ident,$ty:ty)=>{#[derive(Clone)]enum$ident{}impl$crate
            ::__cargo_equip::crates::algebraic::Algebra for$ident{type S=$ty;}};}macro_rules!algebra{($($tt:tt)*)=>(crate
            ::__cargo_equip_macro_def_algebraic_algebra!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_act{($ident:ident,$tar
            :ty,$act:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Act for$ident{type X=$tar;#[inline]fn act(f:&Self::S,x:&Self::X)->Self
            ::X{$act(f,x)}}};}macro_rules!act{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_act!{$($tt)*}
            )}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_monoid{($ident:ident,$e:expr,$op:expr)=>{impl$crate::__cargo_equip::crates
            ::algebraic::Monoid for$ident{#[inline]fn e()->Self::S{$e}#[inline]fn op(x:&Self::S,y:&Self::S)->Self::S{$op(x,y)}}};}macro_rules!monoid{
            ($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_monoid!{$($tt)*}
            )}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_group{($ident:ident,$e:expr,$op:expr,$inv:expr)=>{impl$crate::__cargo_equip
            ::crates::algebraic::Monoid for$ident{#[inline]fn e()->Self::S{$e}#[inline]fn op(x:&Self::S,y:&Self::S)->Self::S{$op(x,y)}}impl$crate
            ::__cargo_equip::crates::algebraic::Group for$ident{#[inline]fn inv(x:&Self::S)->Self::S{$inv(x)}}};}macro_rules!group{($($tt:tt
            )*)=>(crate::__cargo_equip_macro_def_algebraic_group!{$($tt)*})}macro_rules!impl_zero_one{($($t:ty)*)=>{$(impl$crate::__cargo_equip
            ::crates::algebraic::Zero for$t{fn zero()->Self{0}fn is_zero(&self)->bool{*self==0}}impl$crate::__cargo_equip::crates::algebraic::One
            for$t{fn one()->Self{1}fn is_one(&self)->bool{*self==1}})*};}impl_zero_one!(usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128);}
pub mod chminmax {pub use crate::__cargo_equip::macros::chminmax::*;#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_min{($a:expr$
            (,)*)=>{{$a}};($a:expr,$b:expr$(,)*)=>{{std::cmp::min($a,$b)}};($a:expr,$($rest:expr),+$(,)*)=>{{std::cmp::min($a,$crate::__cargo_equip
            ::crates::chminmax::min!($($rest),+))}};}macro_rules!min{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_min!{$($tt)*}
            )}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_max{($a:expr$(,)*)=>{{$a}};($a:expr,$b:expr$(,)*)=>{{std::cmp::max($a,$b)}}
            ;($a:expr,$($rest:expr),+$(,)*)=>{{std::cmp::max($a,$crate::__cargo_equip::crates::chminmax::max!($($rest),+))}};}macro_rules!max{($($tt
            :tt)*)=>(crate::__cargo_equip_macro_def_chminmax_max!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_chmin{($base
            :expr,$($cmps:expr),+$(,)*)=>{{let cmp_min=$crate::__cargo_equip::crates::chminmax::min!($($cmps),+);if$base>cmp_min{$base=cmp_min
            ;true}else{false}}};}macro_rules!chmin{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_chmin!{$($tt)*}
            )}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_chmax{($base:expr,$($cmps:expr),+$(,)*)=>{{let cmp_max=$crate::__cargo_equip
            ::crates::chminmax::max!($($cmps),+);if$base<cmp_max{$base=cmp_max;true}else{false}}};}macro_rules!chmax{($($tt:tt)*)=>(crate
            ::__cargo_equip_macro_def_chminmax_chmax!{$($tt)*})}}
pub mod fast_factorize {use crate::__cargo_equip::preludes::fast_factorize::*;use std::{convert::{TryFrom,TryInto},fmt::Debug,mem::swap,};use
            montgomery_modint::MontgomeryModInt;pub fn is_prime(n:impl TryInto<u64,Error=impl Debug>)->bool{let n:u64=n.try_into().unwrap();if n&1
            ==0{n==2}else if n<=1{false}else if n<1<<30{miller_rabin(n,&[2,7,61])}else{miller_rabin(n,&[2,325,9375,28178,450775,9780504,1795265022]
            )}}pub fn factorize<N,E,F>(n:N)->Vec<N>where N:TryInto<u64,Error=E>+TryFrom<u64,Error=F>+Ord+Copy,E:Debug,F:Debug,{let n=n.try_into
            ().unwrap();let mut f=factorize_(n);f.sort();f.into_iter().map(|x|x.try_into().unwrap()).collect()}pub fn factor_count<N,E,F>(n:N)->Vec<(N
            ,usize)>where N:TryInto<u64,Error=E>+TryFrom<u64,Error=F>+Ord+Copy,E:Debug,F:Debug,{let f=factorize(n);if f.len()==0{return vec![];}let
            mut r=vec![(f[0],0)];for p in f{if r.last().unwrap().0==p{r.last_mut().unwrap().1+=1;}else{r.push((p,1));}}r}pub fn divisors<N,E,F>(n:N
            )->Vec<N>where N:TryInto<u64,Error=E>+TryFrom<u64,Error=F>+Ord+Copy,E:Debug,F:Debug,{let n=n.try_into().unwrap();if n==0{return vec![]
            ;}let fc=factor_count(n);let mut r=vec![1];for(p,c)in fc{for i in 0..r.len(){let mut x=r[i];for _ in 0..c{x*=p;r.push(x);}}}r.sort();r
            .into_iter().map(|x|x.try_into().unwrap()).collect()}fn gcd(mut a:u64,mut b:u64)->u64{while b!=0{a%=b;swap(&mut a,&mut b);}a}fn
            miller_rabin(n:u64,a:&[u64])->bool{MontgomeryModInt::set_modulus(n);let d=(n-1)>>(n-1).trailing_zeros();let e=MontgomeryModInt::new(1);let
            r=MontgomeryModInt::new(n-1);for&a in a{if n<=a{break;}let mut t=d;let mut y=MontgomeryModInt::new(a).pow(t);while t!=n-1&&y!=e&&y!=r{y*=y
            ;t*=2;}if y!=r&&t%2==0{return false;}}true}fn pollard_rho(n:u64)->u64{if n&1==0{return 2;}else if is_prime(n){return n;}let m=1<<(64-n
            .leading_zeros())/8;let o=MontgomeryModInt::new(1);let mut c=o;loop{let f=|x:MontgomeryModInt|x*x+c;let mut x=o;let mut y=MontgomeryModInt
            ::new(2);let mut ys=o;let mut q=o;let mut r=1;let mut g=1;while g==1{x=y;for _ in 0..r{y=f(y);}for k in(0..r).step_by(m){if g!=1{break;}ys
            =y;for _ in 0..m.min(r-k){y=f(y);q*=x-y;}g=gcd(q.val(),n);}r<<=1;}if g==n{g=1;while g==1{ys=f(ys);g=gcd((x-ys).val(),n);}}if g<n{return if
            is_prime(g){g}else if is_prime(n/g){n/g}else{pollard_rho(g)};}c+=o;}}fn factorize_(n:u64)->Vec<u64>{if n<=1{return vec![];};let p
            =pollard_rho(n);if p==n{return vec![p];}let mut r=factorize_(p);r.extend(factorize_(n/p));r}}
pub mod montgomery_modint {use crate::__cargo_equip::preludes::montgomery_modint::*;use std::{convert::TryInto,fmt::Debug,ops::{Add,AddAssign
            ,Mul,MulAssign,Neg,Sub,SubAssign},sync::atomic::{AtomicU64,Ordering::SeqCst},};use algebraic::{One,Zero};struct Montgomery{m:AtomicU64,r
            :AtomicU64,n2:AtomicU64,}impl Montgomery{const fn new()->Self{Self{m:AtomicU64::new(0),r:AtomicU64::new(0),n2:AtomicU64::new(0),}}fn set
            (&self,m:u64){assert!(m<1<<62);assert!(m&1!=0);if self.m.load(SeqCst)==m{return;}let n2=((m as u128).wrapping_neg()%m as u128)as u64;let
            mut r=m;for _ in 0..5{r=r.wrapping_mul(2u64.wrapping_sub(m.wrapping_mul(r)));}assert!(r.wrapping_mul(m)==1);self.m.store(m,SeqCst);self.r
            .store(r,SeqCst);self.n2.store(n2,SeqCst);}fn reduce(&self,x:u128)->u64{let r=self.r.load(SeqCst);let m=self.m.load(SeqCst);(x
            .wrapping_add(((x as u64).wrapping_mul(r.wrapping_neg())as u128).wrapping_mul(m as u128),)>>64)as u64}}static MONTGOMERY:Montgomery
            =Montgomery::new();#[derive(Default,Clone,Copy)]pub struct MontgomeryModInt(u64);impl MontgomeryModInt{pub fn set_modulus(m:u64
            ){MONTGOMERY.set(m);}pub fn modulus()->u64{MONTGOMERY.m.load(SeqCst)}pub fn new(x:u64)->Self{Self(MONTGOMERY.reduce((x as u128
            ).wrapping_add(Self::modulus()as u128).wrapping_mul(MONTGOMERY.n2.load(SeqCst)as u128),),)}pub fn pow(mut self,k:impl TryInto<u128,Error
            =impl Debug>)->Self{let mut k:u128=k.try_into().unwrap();let mut r=Self::new(1);while k>0{if k&1!=0{r*=self;}self*=self;k>>=1;}r}pub fn
            val(self)->u64{let x=MONTGOMERY.reduce(self.0 as u128);let m=Self::modulus();if x>=m{x-m}else{x}}}impl Neg for MontgomeryModInt{type
            Output=Self;fn neg(self)->Self::Output{Self::new(0)-self}}impl AddAssign<Self>for MontgomeryModInt{fn add_assign(&mut self,rhs:Self){let m
            =Self::modulus();self.0=self.0.wrapping_add(rhs.0.wrapping_sub(m*2));if(self.0 as i64)<0{self.0=self.0.wrapping_add(m*2);}}}impl SubAssign
            <Self>for MontgomeryModInt{fn sub_assign(&mut self,rhs:Self){let m=Self::modulus();self.0=self.0.wrapping_sub(rhs.0);if(self.0 as i64
            )<0{self.0=self.0.wrapping_add(m*2);}}}impl MulAssign<Self>for MontgomeryModInt{fn mul_assign(&mut self,rhs:Self){self.0=MONTGOMERY.reduce
            (self.0 as u128*rhs.0 as u128);}}impl Add<Self>for MontgomeryModInt{type Output=Self;fn add(mut self,rhs:Self)->Self::Output{self+=rhs
            ;self}}impl Sub<Self>for MontgomeryModInt{type Output=Self;fn sub(mut self,rhs:Self)->Self::Output{self-=rhs;self}}impl Mul<Self>for
            MontgomeryModInt{type Output=Self;fn mul(mut self,rhs:Self)->Self::Output{self*=rhs;self}}impl PartialEq for MontgomeryModInt{fn eq(&self
            ,other:&Self)->bool{let m=Self::modulus();(if self.0>=m{self.0-m}else{self.0})==(if other.0>=m{other.0-m}else{other.0})}}impl Eq for
            MontgomeryModInt{}impl Zero for MontgomeryModInt{fn zero()->Self{Self(0)}fn is_zero(&self)->bool{self.0==0}}impl One for
            MontgomeryModInt{fn one()->Self{Self(1)}fn is_one(&self)->bool{self==&Self::new(1)}}}
}
pub(crate) mod macros {
pub mod algebraic {pub use crate::{__cargo_equip_macro_def_algebraic_act as act,__cargo_equip_macro_def_algebraic_algebra as algebra
            ,__cargo_equip_macro_def_algebraic_group as group,__cargo_equip_macro_def_algebraic_monoid as monoid};}
pub mod chminmax {pub use crate::{__cargo_equip_macro_def_chminmax_chmax as chmax,__cargo_equip_macro_def_chminmax_chmin as chmin
            ,__cargo_equip_macro_def_chminmax_max as max,__cargo_equip_macro_def_chminmax_min as min};}
pub mod fast_factorize {}
pub mod montgomery_modint {}
}
pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
mod preludes {
pub mod algebraic {}
pub mod chminmax {}
pub mod fast_factorize {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::montgomery_modint;}
pub mod montgomery_modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::algebraic;}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0