#669664 (Rust) No.1556 Power Equality

提出ソース
結果

問題	No.1556 Power Equality
ユーザー	へのく
提出日時	2021-06-25 21:52:12
言語	Rust (1.77.0)
結果	AC
実行時間	1 ms / 2,000 ms
コード長	14,200 bytes
コンパイル時間	1,353 ms
コンパイル使用メモリ	182,964 KB
実行使用メモリ	4,504 KB
最終ジャッジ日時	2023-09-07 15:52:44
合計ジャッジ時間	2,107 ms
ジャッジサーバーID （参考情報）	judge13 / judge14
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	1 ms 4,376 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	AC	1 ms 4,504 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
権限があれば一括ダウンロードができます
ソースコード

raw source code
#![allow(non_snake_case)]
use crate::{modulo::StaticModInt, scanner::Scanner};

const M1: u64 = 754_974_721;
const M2: u64 = 167_772_161;
const M3: u64 = 469_762_049;
modint!(M1);
modint!(M2);
modint!(M3);

type Z1 = StaticModInt<M1>;
type Z2 = StaticModInt<M1>;
type Z3 = StaticModInt<M1>;

fn main() {
    let mut scan = Scanner::new();
    let a = scan.long();
    let b = scan.long();
    println!(
        "{}",
        if Z1::new(a).pow(b) == Z1::new(b).pow(a)
            && Z2::new(a).pow(b) == Z2::new(b).pow(a)
            && Z3::new(a).pow(b) == Z3::new(b).pow(a)
        {
            "Yes"
        } else {
            "No"
        }
    );
}
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()
        }
    }
}

pub mod nums {
    use std::mem::swap;

    pub fn inv_gcd(a: i64, b: i64) -> (i64, i64) {
        let a = a.rem_euclid(b);
        if a == 0 {
            return (b, 0);
        }

        let mut s = b;
        let mut t = a;
        let mut m0 = 0;
        let mut m1 = 1;

        while t != 0 {
            let u = s / t;
            s -= t * u;
            m0 -= m1 * u;

            swap(&mut s, &mut t);
            swap(&mut m0, &mut m1);
        }

        if m0 < 0 {
            m0 += b / s;
        }
        (s, m0)
    }
}
pub mod modulo {
    use crate::nums::inv_gcd;
    use crate::{impl_integer_functions, independent::integer::Int};
    use std::cell::RefCell;
    use std::fmt::Debug;
    use std::marker::PhantomData;
    use std::ops::*;
    use std::sync::atomic::{self, AtomicU32};
    use std::thread::LocalKey;

    pub trait Modulus: 'static + PartialEq + Eq + Copy + Clone + std::hash::Hash + Ord {
        const M: u32;
        const HINT_M_IS_PRIME: bool;
        fn butterfly_cache() -> &'static LocalKey<RefCell<Option<ButterflyCache<Self>>>>;
    }

    pub trait DynamicModulus:
        'static + PartialEq + Eq + Copy + Clone + std::hash::Hash + Ord
    {
        fn state() -> &'static AtomicU32 {
            static M: AtomicU32 = AtomicU32::new(1_000_000_007);
            &M
        }
        fn update(m: u32) {
            Self::state().store(m, atomic::Ordering::SeqCst)
        }
        fn umod() -> u32 {
            Self::state().load(atomic::Ordering::SeqCst)
        }
    }

    #[derive(PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
    pub enum DefaultId {}
    impl DynamicModulus for DefaultId {}

    macro_rules! impl_from_for_modint {
        ($name:ident, $guard: ident, $($tpe:ident),*) => {
            $(
                impl<T: $guard> From<$tpe> for $name<T> {
                    fn from(n: $tpe) -> Self {
                        Self::new(n)
                    }
                }
            )*
        };
    }

    macro_rules! impl_assign {
        ($name:ident, $guard:ident, $($t1:ty, $t2:ty, $fa:ident, $f:ident),*) => {
            $(
                impl<T: $guard> $t1 for $name<T> {
                    type Output = Self;
                    #[inline]
                    fn $f(self, other: Self) -> Self {
                        <Self as ModInt>::$f(self, other)
                    }
                }
                impl<T: $guard> $t2 for $name<T> {
                    #[inline]
                    fn $fa(&mut self, other: Self) {
                        *self = <Self as ModInt>::$f(*self, other);
                    }
                }
            )*
        };
    }

    macro_rules! impl_modint_structs {
        ($name:ident, $guard:ident) => {
            #[derive(PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
            #[repr(transparent)]
            pub struct $name<T> {
                pub val: u32,
                phantom: PhantomData<fn() -> T>,
            }
            impl<T> Debug for $name<T> {
                fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
                    self.val.fmt(f)
                }
            }
            impl<T: $guard> $name<T> {
                #[inline]
                pub fn new<U: Int>(a: U) -> Self {
                    <Self as ModInt>::new(a)
                }
                #[inline]
                pub fn inv(self) -> Self {
                    <Self as ModInt>::inv(self)
                }
                #[inline]
                pub fn raw(val: u32) -> Self {
                    Self {
                        val,
                        phantom: PhantomData,
                    }
                }
                #[inline]
                pub fn pow<U: Int>(self, x: U) -> Self {
                    <Self as ModInt>::pow(self, x)
                }
                #[inline]
                pub fn zero() -> Self {
                    <Self as Int>::zero()
                }
                #[inline]
                pub fn one() -> Self {
                    <Self as Int>::one()
                }
            }
            impl<T> std::fmt::Display for $name<T> {
                fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
                    write!(f, "{}", self.val)
                }
            }
            impl_from_for_modint!(
                $name, $guard, u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize
            );
            impl_assign!(
                $name, $guard, Add, AddAssign, add_assign, add, Sub, SubAssign, sub_assign, sub,
                Mul, MulAssign, mul_assign, mul, Div, DivAssign, div_assign, div, Rem, RemAssign,
                rem_assign, rem
            );
            impl<T: $guard> Int for $name<T> {
                impl_integer_functions!(|s: &Self| s.val, |x| Self::new(x), |s: &Self, n: i64| s
                    .pow(n));
            }
        };
    }

    impl_modint_structs!(StaticModInt, Modulus);
    impl_modint_structs!(DynamicModInt, DynamicModulus);

    #[macro_export]
    macro_rules! modint {
        () => {$crate::modint!(1000000007, true);};
        ($m:literal) => {$crate::modint!($m, true);};
        ($m:literal, $is_prime:literal) => {
            $crate::modint!($m, ModValue, $is_prime);
            #[allow(dead_code)]
            type Z = $crate::modulo::StaticModInt<ModValue>;
        };
        ($name:ident) => {
            $crate::modint!($name, $name, true);
        };
        ($value:expr, $name:ident, $is_prime:literal) => {
            #[derive(Debug, PartialEq, Eq, Copy, Clone, Hash, PartialOrd, Ord)]
            pub enum $name {}
            impl $crate::modulo::Modulus for $name {
                const M: u32 = $value as _;
                const HINT_M_IS_PRIME: bool = $is_prime;
                fn butterfly_cache() -> &'static ::std::thread::LocalKey<::std::cell::RefCell<::std::option::Option<$crate::modulo::ButterflyCache<Self>>>> {
                    thread_local! {
                        static BUTTERFLY_CACHE: ::std::cell::RefCell<::std::option::Option<$crate::modulo::ButterflyCache<$name>>> = ::std::default::Default::default();
                    }
                    &BUTTERFLY_CACHE
                }
            }
        };
    }

    pub type D = DynamicModInt<DefaultId>;

    pub trait ModInt: Int {
        fn new<U: Int>(val: U) -> Self {
            let x = val.to_i128();
            Self::raw(x.rem_euclid(Self::modulus() as i128) as _)
        }
        fn inv(self) -> Self {
            if Self::mod_is_prime() {
                Self::pow(self, Self::modulus() - 2)
            } else {
                let (g, x) = inv_gcd(Self::val(self) as _, Self::modulus() as _);
                if g != 1 {
                    panic!("the multiplicative inverse does not exist");
                } else {
                    Self::new(x)
                }
            }
        }
        fn raw(val: u32) -> Self;
        fn val(self) -> u32;
        fn modulus() -> u32;
        fn mod_is_prime() -> bool;
        fn add(self, other: Self) -> Self {
            let mut ret = self.val() + other.val();
            if ret >= Self::modulus() {
                ret -= Self::modulus();
            }
            Self::raw(ret)
        }
        fn sub(self, other: Self) -> Self {
            let mut ret = self.val().wrapping_sub(other.val());
            if ret >= Self::modulus() {
                ret = ret.wrapping_add(Self::modulus());
            }
            Self::raw(ret)
        }
        fn mul(self, other: Self) -> Self {
            Self::raw(
                (u64::from(self.val()) * u64::from(other.val()) % u64::from(Self::modulus())) as _,
            )
        }
        fn div(self, other: Self) -> Self {
            self * other.inv()
        }
        fn rem(self, other: Self) -> Self {
            Self::raw(self.val() % other.val())
        }
        fn pow<U: Int>(self, x: U) -> Self {
            let mut n = x.to_i64();
            let mut a = self;
            let mut res = Self::raw(1);
            while n > 0 {
                if n & 1 == 1 {
                    res *= a;
                }
                a = a * a;
                n >>= 1;
            }
            res
        }
    }

    impl<M: Modulus> ModInt for StaticModInt<M> {
        fn raw(val: u32) -> Self {
            Self::raw(val)
        }
        fn val(self) -> u32 {
            self.val
        }
        fn modulus() -> u32 {
            M::M
        }
        fn mod_is_prime() -> bool {
            M::HINT_M_IS_PRIME
        }
    }

    impl<M: DynamicModulus> ModInt for DynamicModInt<M> {
        fn raw(val: u32) -> Self {
            Self::raw(val)
        }
        fn val(self) -> u32 {
            self.val
        }
        fn modulus() -> u32 {
            M::umod()
        }
        fn mod_is_prime() -> bool {
            false
        }
    }

    pub struct ButterflyCache<T> {
        pub sum_e: Vec<StaticModInt<T>>,
        pub sum_ie: Vec<StaticModInt<T>>,
    }
}
pub mod independent {
    pub mod integer {
        use std::fmt::Display;
        use std::ops::*;

        pub trait Int:
            Add<Output = Self>
            + Sub<Output = Self>
            + Mul<Output = Self>
            + Div<Output = Self>
            + Rem<Output = Self>
            + AddAssign
            + SubAssign
            + MulAssign
            + DivAssign
            + RemAssign
            + std::hash::Hash
            + PartialEq
            + Eq
            + PartialOrd
            + Ord
            + Copy
            + Display
        {
            fn to_u8(&self) -> u8;
            fn to_u16(&self) -> u16;
            fn to_u32(&self) -> u32;
            fn to_u64(&self) -> u64;
            fn to_u128(&self) -> u128;
            fn to_i8(&self) -> i8;
            fn to_i16(&self) -> i16;
            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 from_u8(x: u8) -> Self;
            fn from_u16(x: u16) -> Self;
            fn from_u32(x: u32) -> Self;
            fn from_u64(x: u64) -> Self;
            fn from_u128(x: u128) -> Self;
            fn from_i8(x: i8) -> Self;
            fn from_i16(x: i16) -> Self;
            fn from_i32(x: i32) -> 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 zero() -> Self;
            fn one() -> Self;
            fn next(&self) -> Self {
                *self + Self::one()
            }
            fn powint(&self, n: i64) -> Self;
        }

        #[macro_export]
        macro_rules! impl_integer_functions {
            ($to_op:expr, $from_op:expr, $pow:expr) => {
                impl_integer_functions!(
                    $to_op, $from_op, $pow,
                    to_u8, from_u8, u8,
                    to_u16, from_u16, u16,
                    to_u32, from_u32, u32,
                    to_u64, from_u64, u64,
                    to_u128, from_u128, u128,
                    to_i8, from_i8, i8,
                    to_i16, from_i16, i16,
                    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_op:expr, $from_op:expr, $pow: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)}
                fn powint(&self, n: i64) -> Self {$pow(self, n)}
            };
        }

        macro_rules! impl_integer {
            ($($tpe:ident),*) => {
                $(
                    impl Int for $tpe {
                        impl_integer_functions!(
                            |s: &Self| *s, |x| x as $tpe, |s: &Self, n: i64| s.pow(n as u32)
                        );
                    }
                )*
            };
        }

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

結果

テストケース

ソースコード
