#1010884 (Rust) No.2380 Sylow P-subgroup

• 問題: No.2380 Sylow P-subgroup
• ユーザー: Haar
• 提出日時: 2024-09-16 04:13:04
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 13,603 bytes
• コンパイル時間: 12,346 ms
• コンパイル使用メモリ: 405,188 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-16 04:13:23
• 合計ジャッジ時間: 13,764 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	1 ms; 5,376 KB
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	1 ms; 5,376 KB

ソースコード

// Bundled at 2024/09/16 04:12:27 +09:00
// Author: Haar

pub mod main {
    use super::*;
    use haar_lib::math::factorial_prime_factor::*;
    use haar_lib::num::const_modint::*;
    #[allow(unused_imports)]
    use haar_lib::{get, input, iter::join_str::*, utils::fastio::*};
    #[allow(unused_imports)]
    use std::cell::{Cell, RefCell};
    #[allow(unused_imports)]
    use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet};
    #[allow(unused_imports)]
    use std::io::Write;
    #[allow(unused_imports)]
    use std::rc::Rc;
    #[derive(Clone, Default)]
    pub struct Problem {}
    impl Problem {
        pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> {
            let mut io = FastIO::new();
            input!(io >> n: u64, p: u64);
            let e = factorial_prime_factor(n, p);
            let ans = ConstModIntBuilder::<998244353>.from_u64(p).pow(e);
            io.writeln(ans);
            Ok(())
        }
    }
}
fn main() {
    main::Problem::default().main().unwrap();
}
use crate as haar_lib;
pub mod iter {
    pub mod join_str {
        pub trait JoinStr: Iterator {
            fn join_str(self, s: &str) -> String
            where
                Self: Sized,
                Self::Item: ToString,
            {
                self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
            }
        }
        impl<I> JoinStr for I where I: Iterator + ?Sized {}
    }
}
pub mod macros {
    pub mod io {
        #[macro_export]
        macro_rules! get {
    ( $in:ident, [$a:tt $(as $to:ty)*; $num:expr] ) => {
        {
            let n = $num;
            (0 .. n).map(|_| get!($in, $a $(as $to)*)).collect::<Vec<_>>()
        }
    };
    ( $in:ident, ($($type:tt $(as $to:ty)*),*) ) => {
        ($(get!($in, $type $(as $to)*)),*)
    };
    ( $in:ident, i8 ) => { $in.read_i64() as i8 };
    ( $in:ident, i16 ) => { $in.read_i64() as i16 };
    ( $in:ident, i32 ) => { $in.read_i64() as i32 };
    ( $in:ident, i64 ) => { $in.read_i64() };
    ( $in:ident, isize ) => { $in.read_i64() as isize };
    ( $in:ident, u8 ) => { $in.read_u64() as u8 };
    ( $in:ident, u16 ) => { $in.read_u64() as u16 };
    ( $in:ident, u32 ) => { $in.read_u64() as u32 };
    ( $in:ident, u64 ) => { $in.read_u64() };
    ( $in:ident, usize ) => { $in.read_u64() as usize };
    ( $in:ident, [char] ) => { $in.read_chars() };
    ( $in:ident, $from:tt as $to:ty ) => { <$to>::from(get!($in, $from)) };
}
        #[macro_export]
        macro_rules! input {
    ( @inner $in:ident, mut $name:ident : $type:tt ) => {
        let mut $name = get!($in, $type);
    };
    ( @inner $in:ident, mut $name:ident : $type:tt as $to:ty ) => {
        let mut $name = get!($in, $type as $to);
    };
    ( @inner $in:ident, $name:ident : $type:tt ) => {
        let $name = get!($in, $type);
    };
    ( @inner $in:ident, $name:ident : $type:tt as $to:ty ) => {
        let $name = get!($in, $type as $to);
    };
    ( $in:ident >> $($($names:ident)* : $type:tt $(as $to:ty)*),* ) => {
        $(input!(@inner $in, $($names)* : $type $(as $to)*);)*
    }
}
    }
}
pub mod math {
    pub mod factorial_prime_factor {
        pub fn factorial_prime_factor(a: u64, p: u64) -> u64 {
            let mut ret = 0;
            let mut q = p;
            while q <= a {
                ret += a / q;
                if let Some(q_) = q.checked_mul(p) {
                    q = q_;
                } else {
                    break;
                }
            }
            ret
        }
    }
}
pub mod num {
    pub mod const_modint {
        pub use crate::num::ff::*;
        use std::{
            fmt,
            fmt::{Debug, Display, Formatter},
            ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign},
        };
        #[derive(Clone, Default, PartialEq, Eq)]
        pub struct ConstModIntBuilder<const M: u32>;
        impl<const M: u32> FF for ConstModIntBuilder<M> {
            type Output = ConstModInt<M>;
            fn from_u64(&self, a: u64) -> Self::Output {
                Self::Output::new_unchecked(if a < M as u64 {
                    a as u32
                } else {
                    (a % M as u64) as u32
                })
            }
            fn from_i64(&self, value: i64) -> Self::Output {
                let value = ((value % M as i64) + M as i64) as u32;
                Self::Output::new(value)
            }
            fn frac(&self, numerator: i64, denominator: i64) -> Self::Output {
                self.from_i64(numerator) * self.from_i64(denominator).inv()
            }
        }
        #[derive(Copy, Clone, PartialEq, Default)]
        pub struct ConstModInt<const M: u32>(u32);
        impl<const M: u32> FFElem for ConstModInt<M> {}
        impl<const M: u32> ConstModInt<M> {
            pub fn new(n: u32) -> Self {
                Self(if n < M { n } else { n % M })
            }
            pub fn to_u32(self) -> u32 {
                self.0
            }
            #[inline]
            fn new_unchecked(value: u32) -> Self {
                Self(value)
            }
            #[inline]
            fn add_internal(self, other: Self) -> Self {
                let a = self.0 + other.0;
                Self::new_unchecked(if a < M { a } else { a - M })
            }
            #[inline]
            fn sub_internal(self, other: Self) -> Self {
                let a = if self.0 < other.0 {
                    self.0 + M - other.0
                } else {
                    self.0 - other.0
                };
                Self::new_unchecked(a)
            }
            #[inline]
            fn mul_internal(self, other: Self) -> Self {
                let a = self.0 as u64 * other.0 as u64;
                Self::new_unchecked(if a < M as u64 {
                    a as u32
                } else {
                    (a % M as u64) as u32
                })
            }
            #[inline]
            fn div_internal(self, other: Self) -> Self {
                self * other.inv_internal()
            }
            #[inline]
            fn inv_internal(self) -> Self {
                self.pow_internal(M as u64 - 2)
            }
            #[inline]
            fn pow_internal(self, mut p: u64) -> Self {
                let mut ret: u64 = 1;
                let mut a = self.0 as u64;
                while p > 0 {
                    if (p & 1) != 0 {
                        ret *= a;
                        ret %= M as u64;
                    }
                    a *= a;
                    a %= M as u64;
                    p >>= 1;
                }
                Self::new_unchecked(ret as u32)
            }
        }
        impl<const M: u32> Pow for ConstModInt<M> {
            type Output = Self;
            fn pow(self, p: u64) -> Self {
                self.pow_internal(p)
            }
        }
        impl<const M: u32> Inv for ConstModInt<M> {
            type Output = Self;
            fn inv(self) -> Self {
                self.inv_internal()
            }
        }
        impl<const M: u32> Display for ConstModInt<M> {
            fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
                write!(f, "{}", self.0)
            }
        }
        impl<const M: u32> Debug for ConstModInt<M> {
            fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
                write!(f, "{} (mod {})", self.0, M)
            }
        }
        impl<const M: u32> From<ConstModInt<M>> for u32 {
            fn from(from: ConstModInt<M>) -> Self {
                from.0
            }
        }
        macro_rules! impl_modint_arith {
    ($tr:ident, $f:ident, $fi:ident, $tr_a:ident, $f_a:ident, $op:tt) => {
        impl<const M: u32> $tr for ConstModInt<M> {
            type Output = Self;
            #[inline]
            fn $f(self, other: Self) -> Self {
                self.$fi(other)
            }
        }
        impl<const M: u32> $tr_a for ConstModInt<M> {
            #[inline]
            fn $f_a(&mut self, other: Self) {
                *self = *self $op other;
            }
        }
    }
}
        impl_modint_arith!(Add, add, add_internal, AddAssign, add_assign, +);
        impl_modint_arith!(Sub, sub, sub_internal, SubAssign, sub_assign, -);
        impl_modint_arith!(Mul, mul, mul_internal, MulAssign, mul_assign, *);
        impl_modint_arith!(Div, div, div_internal, DivAssign, div_assign, /);
        impl<const M: u32> Neg for ConstModInt<M> {
            type Output = Self;
            fn neg(self) -> Self {
                Self::new_unchecked(if self.0 == 0 { 0 } else { M - self.0 })
            }
        }
    }
    pub mod ff {
        use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};
        pub trait Pow {
            type Output;
            fn pow(self, p: u64) -> Self::Output;
        }
        pub trait Inv {
            type Output;
            fn inv(self) -> Self::Output;
        }
        #[allow(clippy::wrong_self_convention)]
        pub trait FF: Clone {
            type Output;
            fn from_u64(&self, a: u64) -> Self::Output;
            fn from_i64(&self, a: i64) -> Self::Output;
            fn frac(&self, a: i64, b: i64) -> Self::Output;
        }
        pub trait FFElem:
            Pow<Output = Self>
            + Inv<Output = Self>
            + Add<Output = Self>
            + AddAssign
            + Sub<Output = Self>
            + SubAssign
            + Mul<Output = Self>
            + MulAssign
            + Div<Output = Self>
            + DivAssign
            + Neg<Output = Self>
            + Copy
            + Clone
            + PartialEq
            + Sized
        {
        }
    }
}
pub mod utils {
    pub mod fastio {
        use std::fmt::Display;
        use std::io::{Read, Write};
        pub struct FastIO {
            in_bytes: Vec<u8>,
            in_cur: usize,
            out_buf: std::io::BufWriter<std::io::Stdout>,
        }
        impl FastIO {
            pub fn new() -> Self {
                let mut s = vec![];
                std::io::stdin().read_to_end(&mut s).unwrap();
                let cout = std::io::stdout();
                Self {
                    in_bytes: s,
                    in_cur: 0,
                    out_buf: std::io::BufWriter::new(cout),
                }
            }
            #[inline]
            pub fn getc(&mut self) -> Option<u8> {
                if self.in_cur < self.in_bytes.len() {
                    self.in_cur += 1;
                    Some(self.in_bytes[self.in_cur])
                } else {
                    None
                }
            }
            #[inline]
            pub fn peek(&self) -> Option<u8> {
                if self.in_cur < self.in_bytes.len() {
                    Some(self.in_bytes[self.in_cur])
                } else {
                    None
                }
            }
            #[inline]
            pub fn skip(&mut self) {
                while self.peek().map_or(false, |c| c.is_ascii_whitespace()) {
                    self.in_cur += 1;
                }
            }
            pub fn read_u64(&mut self) -> u64 {
                self.skip();
                let mut ret: u64 = 0;
                while self.peek().map_or(false, |c| c.is_ascii_digit()) {
                    ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64;
                    self.in_cur += 1;
                }
                ret
            }
            pub fn read_u32(&mut self) -> u32 {
                self.read_u64() as u32
            }
            pub fn read_usize(&mut self) -> usize {
                self.read_u64() as usize
            }
            pub fn read_i64(&mut self) -> i64 {
                self.skip();
                let mut ret: i64 = 0;
                let minus = if self.peek() == Some(b'-') {
                    self.in_cur += 1;
                    true
                } else {
                    false
                };
                while self.peek().map_or(false, |c| c.is_ascii_digit()) {
                    ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64;
                    self.in_cur += 1;
                }
                if minus {
                    ret = -ret;
                }
                ret
            }
            pub fn read_i32(&mut self) -> i32 {
                self.read_i64() as i32
            }
            pub fn read_isize(&mut self) -> isize {
                self.read_i64() as isize
            }
            pub fn read_f64(&mut self) -> f64 {
                self.read_chars()
                    .into_iter()
                    .collect::<String>()
                    .parse()
                    .unwrap()
            }
            pub fn read_chars(&mut self) -> Vec<char> {
                self.skip();
                let mut ret = vec![];
                while self.peek().map_or(false, |c| c.is_ascii_graphic()) {
                    ret.push(self.in_bytes[self.in_cur] as char);
                    self.in_cur += 1;
                }
                ret
            }
            pub fn write<T: Display>(&mut self, s: T) {
                self.out_buf.write_all(format!("{}", s).as_bytes()).unwrap();
            }
            pub fn writeln<T: Display>(&mut self, s: T) {
                self.write(s);
                self.out_buf.write_all(&[b'\n']).unwrap();
            }
        }
        impl Drop for FastIO {
            fn drop(&mut self) {
                self.out_buf.flush().unwrap();
            }
        }
    }
}