結果
| 問題 |
No.2380 Sylow P-subgroup
|
| コンテスト | |
| ユーザー |
 Haar
|
| 提出日時 | 2024-09-16 04:13:04 |
| 言語 | Rust (1.83.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 14 |
ソースコード
// 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();
}
}
}
}