#681217 (Rust) No.1616 Joke

提出ソース
結果

問題	No.1616 Joke
ユーザー	へのく
提出日時	2021-07-22 21:25:17
言語	Rust (1.77.0)
結果	AC
実行時間	1 ms / 2,000 ms
コード長	22,593 bytes
コンパイル時間	1,751 ms
コンパイル使用メモリ	173,628 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-09-24 15:29:48
合計ジャッジ時間	2,795 ms
ジャッジサーバーID （参考情報）	judge15 / judge12
このコードへのチャレンジ（β）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,376 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	1 ms 4,380 KB
testcase_04	AC	1 ms 4,380 KB
testcase_05	AC	1 ms 4,380 KB
testcase_06	AC	1 ms 4,376 KB
testcase_07	AC	1 ms 4,376 KB
testcase_08	AC	1 ms 4,376 KB
testcase_09	AC	1 ms 4,376 KB
testcase_10	AC	1 ms 4,376 KB
testcase_11	AC	1 ms 4,380 KB
testcase_12	AC	1 ms 4,376 KB
testcase_13	AC	1 ms 4,376 KB
testcase_14	AC	1 ms 4,380 KB
testcase_15	AC	1 ms 4,380 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#![allow(non_snake_case)]
#[allow(unused_imports)]
use crate::{arraylist::List, scanner::Scanner};
use crate::{geometry::fraction::Frac, primes::utils::divisors};

fn main() {
    let ret = calc();
    println!("{}", ret);
}
fn calc() -> i64 {
    let mut scan = Scanner::new();
    let n = scan.long();
    let a = divisors(n);
    let b = a.map(|x| Frac::new(1, x));
    let c = Frac::new(a.sum(), 1) / b.fold(Frac::zero(), |acc, x| (acc + x).reduced());
    c.reduced().numer
}
pub mod arraylist {

    use std::ops::*;
    use std::slice::Iter;

    use std::fmt::Formatter;
    use std::iter::FromIterator;

    use crate::independent::integer::Num;

    #[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
    pub struct List<T> {
        pub data: Vec<T>,
    }

    impl<T> List<T> {
        #[inline]
        pub fn new() -> List<T> {
            List { data: vec![] }
        }

        #[inline]
        pub fn push(&mut self, item: T) {
            self.data.push(item);
        }
    }

    macro_rules! impl_idx {
        ($($tpe:ty, $t:ident [$($output:tt)+], $slf:ident, $index:ident, $f:expr),*) => {
            $(impl<$t> Index<$tpe> for List<$t> {
                type Output = $($output)+;
                #[inline]
                fn index(&$slf, $index: $tpe) -> &Self::Output {$f}
            })*
            $(impl<$t> Index<$tpe> for lst<$t> {
                type Output = $($output)+;
                #[inline]
                fn index(&$slf, $index: $tpe) -> &Self::Output {$f}
            })*
        }
    }

    macro_rules! impl_idx_mut {
        ($($tpe:ty, $slf:ident, $index:ident, $f:expr),*) => {
            $(impl<T> IndexMut<$tpe> for List<T> {
                #[inline]
                fn index_mut(&mut $slf, $index: $tpe) -> &mut Self::Output {$f}
            })*
            $(impl<T> IndexMut<$tpe> for lst<T> {
                #[inline]
                fn index_mut(&mut $slf, $index: $tpe) -> &mut Self::Output {$f}
            })*
        };
    }

    macro_rules! impl_idx_slice {
        ($($tpe:ty),*) => {
            impl_idx!($($tpe, T [lst<T>], self, i, self.as_slice(i)),*);
            impl_idx_mut!($($tpe, self, i, self.as_slice_mut(i)),*);
        };
    }

    impl_idx! {
        isize, T [T], self, i, self.at(i),
        char, T [T], self, i, self.at(i as isize - 'a' as isize)
    }

    impl_idx_slice! {
        Range<isize>, RangeTo<isize>, RangeFrom<isize>, RangeFull, RangeInclusive<isize>, RangeToInclusive<isize>
    }

    impl_idx_mut! {
        isize, self, i, self.at_mut(i),
        char, self, i, self.at_mut(i as isize - 'a' as isize)
    }

    impl<T> FromIterator<T> for List<T> {
        #[inline]
        fn from_iter<U: IntoIterator<Item = T>>(iter: U) -> Self {
            List {
                data: iter.into_iter().collect(),
            }
        }
    }

    impl<T> IntoIterator for List<T> {
        type Item = T;
        type IntoIter = std::vec::IntoIter<T>;

        #[inline]
        fn into_iter(self) -> std::vec::IntoIter<T> {
            self.data.into_iter()
        }
    }

    macro_rules! impl_traits {
        ($($tpe:tt),*) => {
            $(
                impl<T: std::fmt::Display> std::fmt::Display for $tpe<T> {
                    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
                        write!(f, "{}", self.iter().map(|x| format!("{}", x)).collect::<Vec<_>>().join(" "))
                    }
                }

                impl<T: std::fmt::Debug> std::fmt::Debug for $tpe<T> {
                    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
                        self.data.fmt(f)
                    }
                }

                impl<'a, T> IntoIterator for &'a $tpe<T> {
                    type Item = &'a T;
                    type IntoIter = Iter<'a, T>;

                    #[inline]
                    fn into_iter(self) -> Iter<'a, T> {
                        self.iter()
                    }
                }
            )*
        };
    }

    impl_traits!(List, lst);

    impl<T> From<Vec<T>> for List<T> {
        #[inline]
        fn from(vec: Vec<T>) -> Self {
            List { data: vec }
        }
    }

    impl<T: Clone> From<&[T]> for List<T> {
        #[inline]
        fn from(slice: &[T]) -> Self {
            slice.iter().cloned().collect()
        }
    }

    impl<T> Deref for List<T> {
        type Target = lst<T>;

        #[inline]
        fn deref(&self) -> &lst<T> {
            lst::new(&self.data)
        }
    }

    impl<T> DerefMut for List<T> {
        #[inline]
        fn deref_mut(&mut self) -> &mut lst<T> {
            lst::new_mut(&mut self.data)
        }
    }

    #[macro_export]
    macro_rules! list {
        () => { $crate::arraylist::List::new() };
        ($($v:expr),+ $(,)?) => { $crate::arraylist::List::from([$($v),+].to_vec()) };
        ($v:expr; $a:expr) => { $crate::arraylist::List::init($v, $a)};
        ($v:expr; $a:expr; $($rest:expr);+) => { $crate::arraylist::List::init(list!($v; $($rest);+), $a) };
    }

    #[allow(non_camel_case_types)]
    #[derive(PartialEq, Eq, PartialOrd, Ord)]
    #[repr(transparent)]
    pub struct lst<T> {
        data: [T],
    }

    impl<T> lst<T> {
        #[inline]
        pub fn new(slice: &[T]) -> &Self {
            unsafe { &*(slice as *const [T] as *const Self) }
        }
        #[inline]
        pub fn new_mut(slice: &mut [T]) -> &mut Self {
            unsafe { &mut *(slice as *mut [T] as *mut Self) }
        }

        #[inline]
        fn at(&self, index: isize) -> &T {
            if cfg!(debug_assertions) {
                self.data.index(index as usize)
            } else {
                unsafe { self.data.get_unchecked(index as usize) }
            }
        }
        #[inline]
        fn at_mut(&mut self, index: isize) -> &mut T {
            if cfg!(debug_assertions) {
                self.data.index_mut(index as usize)
            } else {
                unsafe { self.data.get_unchecked_mut(index as usize) }
            }
        }
        #[inline]
        pub fn as_slice(&self, range: impl RangeBounds<isize>) -> &lst<T> {
            if cfg!(debug_assertions) {
                lst::new(self.data.index(self.rgm(range)))
            } else {
                unsafe { lst::new(self.data.get_unchecked(self.rgm(range))) }
            }
        }
        #[inline]
        pub fn as_slice_mut(&mut self, range: impl RangeBounds<isize>) -> &mut lst<T> {
            if cfg!(debug_assertions) {
                lst::new_mut(self.data.index_mut(self.rgm(range)))
            } else {
                let r = self.rgm(range);
                unsafe { lst::new_mut(self.data.get_unchecked_mut(r)) }
            }
        }

        #[inline]
        pub fn cloned(&self) -> std::iter::Cloned<Iter<T>>
        where
            T: Clone,
        {
            self.iter().cloned()
        }

        #[inline]
        pub fn map<B, F>(&self, f: F) -> List<B>
        where
            T: Clone,
            F: FnMut(T) -> B,
        {
            self.cloned().map(f).collect()
        }

        #[inline]
        pub fn fold<B, F>(&self, init: B, f: F) -> B
        where
            T: Clone,
            F: FnMut(B, T) -> B,
        {
            self.cloned().fold(init, f)
        }

        #[inline]
        pub fn sum(&self) -> T
        where
            T: Num,
        {
            self.cloned().fold(T::zero(), |acc, x| acc + x)
        }

        #[inline]
        fn rgm(&self, r: impl RangeBounds<isize>) -> Range<usize> {
            (match r.start_bound() {
                Bound::Included(x) => *x as usize,
                Bound::Excluded(x) => *x as usize + 1,
                _ => 0,
            })
            .max(0)..(match r.end_bound() {
                Bound::Included(x) => *x as usize + 1,
                Bound::Excluded(x) => *x as usize,
                _ => self.data.len(),
            })
            .min(self.data.len())
        }
    }

    impl lst<isize> {}

    impl<T> Deref for lst<T> {
        type Target = [T];
        #[inline]
        fn deref(&self) -> &[T] {
            &self.data
        }
    }

    impl<T> DerefMut for lst<T> {
        #[inline]
        fn deref_mut(&mut self) -> &mut [T] {
            &mut self.data
        }
    }

    impl<'a, T> From<&'a [T]> for &'a lst<T> {
        #[inline]
        fn from(slice: &'a [T]) -> Self {
            lst::new(slice)
        }
    }
}
pub mod geometry {
    pub mod fraction {
        use crate::{
            impl_num_functions,
            independent::integer::{Int, Num},
        };
        use std::{
            self,
            cmp::{Ordering, Ordering::*},
            fmt::Display,
            ops::*,
        };

        #[derive(Debug, Clone, Copy)]
        pub struct Frac<T> {
            pub numer: T,
            pub denom: T,
        }

        impl<T: Int> Default for Frac<T> {
            fn default() -> Self {
                Self::new_raw(T::zero(), T::one())
            }
        }

        impl<T: Int> Display for Frac<T> {
            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
                write!(f, "{}/{}", self.numer, self.denom)
            }
        }

        impl<T: Int> PartialEq for Frac<T> {
            fn eq(&self, other: &Self) -> bool {
                self.cmp(other) == Equal
            }
        }

        impl<T: Int> Eq for Frac<T> {}

        impl<T: Int> Ord for Frac<T> {
            fn cmp(&self, other: &Self) -> Ordering {
                if self.denom == other.denom {
                    let ord = self.numer.cmp(&other.numer);
                    return if self.denom < T::zero() {
                        ord.reverse()
                    } else {
                        ord
                    };
                }
                if self.numer == other.numer {
                    if self.numer == T::zero() {
                        return Equal;
                    }
                    let ord = self.denom.cmp(&other.denom);
                    return if self.numer < T::zero() {
                        ord
                    } else {
                        ord.reverse()
                    };
                }
                if let Some((a, b)) = self
                    .numer
                    .cmul(other.denom)
                    .and_then(|a| self.denom.cmul(other.numer).map(|b| (a, b)))
                {
                    return a.cmp(&b);
                }

                let (self_int, self_rem) = self.div_mod_floor();
                let (other_int, other_rem) = self.div_mod_floor();
                match self_int.cmp(&other_int) {
                    Greater => Greater,
                    Less => Less,
                    Equal => match (self_rem == T::zero(), other_rem == T::zero()) {
                        (true, true) => Equal,
                        (true, false) => Less,
                        (false, true) => Greater,
                        (false, false) => {
                            let self_recip = Self::new_raw(self.denom, self_rem);
                            let other_recip = Self::new_raw(other.denom, other_rem);
                            self_recip.cmp(&other_recip).reverse()
                        }
                    },
                }
            }
        }

        impl<T: Int> PartialOrd for Frac<T> {
            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
                Some(self.cmp(other))
            }
        }

        impl<T: Int> Frac<T> {
            pub fn new_raw(numer: T, denom: T) -> Self {
                Self { numer, denom }
            }
            pub fn new(numer: T, denom: T) -> Self {
                if denom == T::zero() {
                    panic!("denominator == 0")
                }
                if numer == T::zero() {
                    return Self::new_raw(numer, T::one());
                }
                Self::new_raw(numer, denom).reduced()
            }
            pub fn new_int(numer: T) -> Self {
                Self {
                    numer,
                    denom: T::one(),
                }
            }
            pub fn zero() -> Self {
                Self::new_raw(T::zero(), T::one())
            }

            pub fn floor(&self) -> T {
                if *self < Self::zero() {
                    (self.numer - self.denom + T::one()) / self.denom
                } else {
                    self.numer / self.denom
                }
            }

            pub fn reduce(&mut self) {
                let g = gcd(self.numer, self.denom);
                self.numer /= g;
                self.denom /= g;
                if self.denom < T::zero() {
                    self.numer = T::zero() - self.numer;
                    self.denom = T::zero() - self.denom;
                }
            }

            pub fn reduced(&self) -> Self {
                let mut t = *self;
                t.reduce();
                t
            }

            fn div_mod_floor(&self) -> (T, T) {
                if self.numer < T::zero() {
                    (
                        T::zero() - (self.numer + self.denom - T::one()) / self.denom,
                        self.denom + self.numer % self.denom,
                    )
                } else {
                    (self.numer / self.denom, self.numer % self.denom)
                }
            }
        }

        fn gcd<T: Int>(a: T, b: T) -> T {
            if b == T::zero() {
                a
            } else {
                gcd(b, a % b)
            }
        }

        fn lcm<T: Int>(a: T, b: T) -> T {
            a / gcd(a, b) * b
        }

        impl<T: Int> Num for Frac<T> {
            impl_num_functions! {
                |s: &Self| s.floor().to_i128(), |x| Self::new_int(T::from_i128(x as _)), |s: Self| if s < Self::zero() {-1} else if s > Self::zero() {1} else {0}
            }
        }

        impl<T: Int> AddAssign for Frac<T> {
            fn add_assign(&mut self, other: Self) {
                if self.denom == other.denom {
                    self.numer += other.numer
                } else {
                    let lcm = lcm(self.denom, other.denom);
                    let lhs_numer = self.numer * (lcm / self.denom);
                    let rhs_numer = other.numer * (lcm / other.denom);
                    self.numer = lhs_numer + rhs_numer;
                    self.denom = lcm;
                }
            }
        }

        impl<T: Int> DivAssign for Frac<T> {
            fn div_assign(&mut self, other: Self) {
                let gcd_ac = gcd(self.numer, other.numer);
                let gcd_bd = gcd(self.denom, other.denom);
                self.numer /= gcd_ac;
                self.numer *= other.denom / gcd_bd;
                self.denom /= gcd_bd;
                self.denom *= other.numer / gcd_ac;
            }
        }

        impl<T: Int> MulAssign for Frac<T> {
            fn mul_assign(&mut self, other: Self) {
                let gcd_ad = gcd(self.numer, other.denom);
                let gcd_bc = gcd(self.denom, other.numer);
                self.numer /= gcd_ad;
                self.numer *= other.numer / gcd_bc;
                self.denom /= gcd_bc;
                self.denom *= other.denom / gcd_ad;
            }
        }

        impl<T: Int> RemAssign for Frac<T> {
            fn rem_assign(&mut self, other: Self) {
                if self.denom == other.denom {
                    self.numer %= other.numer
                } else {
                    let lcm = lcm(self.denom, other.denom);
                    let lhs_numer = self.numer * (lcm / self.denom);
                    let rhs_numer = other.numer * (lcm / other.denom);
                    self.numer = lhs_numer % rhs_numer;
                    self.denom = lcm;
                }
            }
        }

        impl<T: Int> SubAssign for Frac<T> {
            fn sub_assign(&mut self, other: Self) {
                if self.denom == other.denom {
                    self.numer -= other.numer;
                } else {
                    let lcm = lcm(self.denom, other.denom);
                    let lhs_numer = self.numer * (lcm / self.denom);
                    let rhs_numer = other.numer * (lcm / other.denom);
                    self.numer = lhs_numer - rhs_numer;
                    self.denom = lcm;
                }
            }
        }

        macro_rules! impl_ops {
            ($($tpe:ident, $fname:ident, $fname2:tt),*) => {
                $(impl<T: Int> $tpe for Frac<T> {
                    type Output = Self;
                    fn $fname(self, other: Self) -> Self {
                        let mut ret = self.clone();
                        ret $fname2 other; ret
                    }
                })*
            };
        }

        impl_ops!(Add, add, +=, Sub, sub, -=, Mul, mul, *=, Div, div, /=, Rem, rem, %=);
    }
}
pub mod independent {
    pub mod integer {
        use std::fmt::Debug;
        use std::fmt::Display;
        use std::ops::*;

        pub trait Num:
            Add<Output = Self>
            + Sub<Output = Self>
            + Mul<Output = Self>
            + Div<Output = Self>
            + AddAssign
            + SubAssign
            + MulAssign
            + DivAssign
            + PartialEq
            + PartialOrd
            + Copy
            + Debug
            + Display
        {
            fn to_u32(&self) -> u32;
            fn to_u64(&self) -> u64;
            fn to_u128(&self) -> u128;
            fn to_i32(&self) -> i32;
            fn to_i64(&self) -> i64;
            fn to_i128(&self) -> i128;
            fn to_usize(&self) -> usize;
            fn to_isize(&self) -> isize;
            fn to_f64(&self) -> f64;
            fn from_i32(x: i32) -> Self;
            fn from_u32(x: u32) -> Self;
            fn from_u64(x: u64) -> Self;
            fn from_u128(x: u128) -> Self;
            fn from_i64(x: i64) -> Self;
            fn from_i128(x: i128) -> Self;
            fn from_usize(x: usize) -> Self;
            fn from_isize(x: isize) -> Self;
            fn from_f64(x: f64) -> Self;
            fn zero() -> Self;
            fn one() -> Self;
            fn approx_sign(self) -> i32;
            fn approx_eq(self, other: Self) -> bool {
                (self - other).approx_sign() == 0
            }
        }

        pub trait Int: Num + Rem<Output = Self> + RemAssign + Ord {
            fn powint(&self, n: i64) -> Self;
            fn cmul(&self, b: Self) -> Option<Self>;
        }

        pub trait Float: Num {}

        #[macro_export]
        macro_rules! impl_num_functions {
            ($to_op:expr, $from_op:expr, $appx_op:expr) => {
                impl_num_functions!(
                    $to_op, $from_op,
                    to_u32, from_u32, u32,
                    to_u64, from_u64, u64,
                    to_u128, from_u128, u128,
                    to_i32, from_i32, i32,
                    to_i64, from_i64, i64,
                    to_i128, from_i128, i128,
                    to_usize, from_usize, usize,
                    to_isize, from_isize, isize,
                    to_f64, from_f64, f64
                );
                fn approx_sign(self) -> i32 {($appx_op)(self)}
            };
            ($to_op:expr, $from_op:expr, $($tofn:ident, $fromfn:ident, $tpe:ident),*) => {
                $(
                    fn $tofn(&self) -> $tpe {
                        $to_op(self) as $tpe
                    }
                    fn $fromfn(x: $tpe) -> Self {
                        $from_op(x)
                    }
                )*
                fn zero() -> Self {$from_op(0)}
                fn one() -> Self {$from_op(1)}
            };
        }

        macro_rules! impl_num_int {
            ($($tpe:ident),*) => {
                $(
                    impl Num for $tpe {
                        impl_num_functions!(
                            |s: &Self| *s, |x| x as $tpe, |s: Self| if s < Self::zero() {-1} else if s > Self::zero() {1} else {0}
                        );
                    }
                    impl Int for $tpe {
                        fn powint(&self, n: i64) -> Self {
                            self.pow(n as u32) as $tpe
                        }
                        fn cmul(&self, b: Self) -> Option<Self> {self.checked_mul(b)}
                    }
                )*
            };
        }

        impl_num_int!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize);

        pub const EPS: f64 = 1e-6;

        impl Num for f64 {
            impl_num_functions!(|s: &Self| *s, |x| x as f64, |s: Self| if s < -EPS {
                -1
            } else if s > EPS {
                1
            } else {
                0
            });
        }
        impl Float for f64 {}
    }
}

pub mod primes {
    pub mod utils {
        use crate::arraylist::List;

        pub fn divisors(n: i64) -> List<i64> {
            let mut ret = List::new();
            for i in (1..).take_while(|i| i * i <= n) {
                if n % i == 0 {
                    ret.push(i);
                    if i != n / i {
                        ret.push(n / i);
                    }
                }
            }
            ret
        }
    }
}
pub mod types {

    pub use crate::arraylist::List as Seq;
    #[allow(non_camel_case_types)]
    pub type idx = isize;
    pub use crate::list as seq;

    pub use std::collections::hash_map as map;
    pub use std::collections::HashMap as Map;
}
pub mod scanner {
    use std::io::{stdin, BufReader, Bytes, Read, Stdin};

    use std::str::FromStr;

    pub struct Scanner {
        buf: Bytes<BufReader<Stdin>>,
    }

    impl Scanner {
        pub fn new() -> Scanner {
            Scanner {
                buf: BufReader::new(stdin()).bytes(),
            }
        }

        #[inline]
        fn token<T: std::iter::FromIterator<char>>(&mut self) -> T {
            self.buf
                .by_ref()
                .map(|c| c.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        }

        #[inline]
        pub fn read<T: FromStr>(&mut self) -> T {
            self.string().parse().ok().unwrap()
        }

        #[inline]
        pub fn string(&mut self) -> String {
            self.token()
        }

        #[inline]
        pub fn long(&mut self) -> i64 {
            self.read()
        }
    }
}
yukicoder

結果

テストケース

ソースコード
