結果
| 問題 | No.187 中華風 (Hard) |
| ユーザー |
 tayu0110
|
| 提出日時 | 2023-01-22 02:04:53 |
| 言語 | Rust (1.77.0) |
| 結果 |
AC
|
| 実行時間 | 137 ms / 3,000 ms |
| コード長 | 37,853 bytes |
| コンパイル時間 | 4,483 ms |
| コンパイル使用メモリ | 171,724 KB |
| 実行使用メモリ | 4,384 KB |
| 最終ジャッジ日時 | 2023-09-06 12:42:21 |
| 合計ジャッジ時間 | 5,054 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,376 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 98 ms
4,376 KB |
| testcase_03 | AC | 97 ms
4,376 KB |
| testcase_04 | AC | 137 ms
4,376 KB |
| testcase_05 | AC | 133 ms
4,380 KB |
| testcase_06 | AC | 133 ms
4,376 KB |
| testcase_07 | AC | 132 ms
4,384 KB |
| testcase_08 | AC | 88 ms
4,376 KB |
| testcase_09 | AC | 85 ms
4,376 KB |
| testcase_10 | AC | 87 ms
4,380 KB |
| testcase_11 | AC | 124 ms
4,380 KB |
| testcase_12 | AC | 125 ms
4,380 KB |
| testcase_13 | AC | 21 ms
4,376 KB |
| testcase_14 | AC | 21 ms
4,380 KB |
| testcase_15 | AC | 88 ms
4,380 KB |
| testcase_16 | AC | 87 ms
4,380 KB |
| testcase_17 | AC | 1 ms
4,380 KB |
| testcase_18 | AC | 1 ms
4,380 KB |
| testcase_19 | AC | 1 ms
4,376 KB |
| testcase_20 | AC | 94 ms
4,380 KB |
| testcase_21 | AC | 1 ms
4,380 KB |
| testcase_22 | AC | 121 ms
4,376 KB |
| testcase_23 | AC | 1 ms
4,376 KB |
| testcase_24 | AC | 1 ms
4,376 KB |
ソースコード
// https://yukicoder.me/problems/448
pub use __cargo_equip::prelude::*;
use iolib::scan;
use math::garner_prechecked;
const MOD: i64 = 1000_000_007;
fn main() {
scan!(n: usize, p: [(i64, i64); n]);
let (a, p) = p.into_iter().unzip::<i64, i64, Vec<_>, Vec<_>>();
let f = a.iter().all(|a| *a == 0);
if let Some((res, lcm)) = garner_prechecked(&a, &p, MOD) {
if f {
println!("{}", lcm)
} else {
println!("{}", res)
}
} else {
println!("-1")
}
}
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod iolib {
pub use crate::__cargo_equip::macros::iolib::*;
mod input {
use std::io::{BufRead, Read, StdinLock};
use std::ptr::copy_nonoverlapping;
use std::slice::from_raw_parts_mut;
const BUF_SIZE: usize = 1 << 18;
pub struct FastInput {
head: usize,
tail: usize,
interactive: bool,
eof: bool,
buf: [u8; BUF_SIZE],
}
impl FastInput {
pub const fn new() -> Self {
Self {
head: 0,
tail: 0,
interactive: false,
eof: false,
buf: [0; 1 << 18],
}
}
#[inline]
pub fn set_interactive(&mut self) { self.interactive = true; }
#[inline]
unsafe fn load(&mut self) {
// BUF: [buf_head............head....tail...]
let buf_head = self.buf.as_mut_ptr();
// src = buf_head + head
// so, src = &head
let src = buf_head.add(self.head);
let count = self.tail - self.head;
// <before>
// BUF: [buf_head............[head....tail]...]
// ^ copy |
// |___________________|
// <after>
// BUF: [[head....tail].............[head....tail]...]
copy_nonoverlapping(src, buf_head, count);
// let buf = from_raw_parts_mut(buf_head.add(count), BUF_SIZE - count);
// self.tail = count + STDIN_SOURCE().read(buf).unwrap();
self.tail = count
+ if !self.interactive {
let buf = from_raw_parts_mut(buf_head.add(count), BUF_SIZE - count);
let res = STDIN_SOURCE().read(buf).unwrap();
self.eof |= res == 0;
res
} else {
let mut buf = vec![];
let res = STDIN_SOURCE().read_until(b'\n', &mut buf).unwrap();
copy_nonoverlapping(buf.as_ptr(), buf_head.add(count), res);
res
};
self.head = 0;
if self.tail < BUF_SIZE {
self.buf[self.tail] = b' ';
}
}
#[inline]
fn readc(&mut self) -> u8 {
let res = self.buf[self.head];
self.head += 1;
res
}
#[inline(always)]
fn refill_buffer(&mut self) {
if self.eof {
return;
}
if !self.interactive && self.head + 32 > self.tail {
unsafe { self.load() }
} else if self.interactive && self.head >= self.tail {
unsafe { self.load() }
}
}
#[inline]
pub fn read_u64(&mut self) -> u64 {
self.refill_buffer();
let mut x = 0u64;
while !self.buf[self.head].is_ascii_whitespace() {
x = x * 10 + (self.buf[self.head] - b'0') as u64;
self.head += 1;
}
self.head += 1;
x
}
#[inline]
pub fn read_i64(&mut self) -> i64 {
self.refill_buffer();
if self.buf[self.head] == b'-' {
self.head += 1;
-(self.read_u64() as i64)
} else {
self.read_u64() as i64
}
}
#[inline]
pub fn read_char(&mut self) -> char {
self.refill_buffer();
let c = self.readc();
if self.buf[self.head].is_ascii_whitespace() {
self.head += 1;
}
c as char
}
#[inline]
pub fn read_string(&mut self) -> String {
if self.interactive {
let mut buf = String::new();
std::io::BufReader::read_line(&mut std::io::BufReader::new(unsafe { STDIN_SOURCE() }), &mut buf).unwrap();
return buf;
}
self.refill_buffer();
let mut tail = self.head;
while tail < self.tail && !self.buf[tail].is_ascii_whitespace() {
tail += 1;
}
let mut res = String::from_utf8_lossy(&self.buf[self.head..tail]).into_owned();
self.head = tail;
if tail == self.tail {
res.push_str(&self.read_string());
} else {
self.head += 1;
}
res
}
}
macro_rules! impl_read_signed_integeer {
( $( { $t:ty, $fname:ident } )* ) => {
$(impl FastInput {
#[inline]
pub fn $fname(&mut self) -> $t { self.read_i64() as $t }
})*
};
}
macro_rules! impl_read_unsigned_integeer {
( $( { $t:ty, $fname:ident } )* ) => {
$(impl FastInput {
#[inline]
pub fn $fname (&mut self) -> $t { self.read_u64() as $t }
})*
};
}
impl_read_signed_integeer!({i8, read_i8} {i16, read_i16} {i32, read_i32} {i128, read_i128} {isize, read_isize});
impl_read_unsigned_integeer!({u8, read_u8} {u16, read_u16} {u32, read_u32} {u128, read_u128} {usize, read_usize});
fn init() -> &'static mut StdinLock<'static> {
let stdin = Box::leak(Box::new(std::io::stdin()));
unsafe {
STDIN = Box::leak(Box::new(stdin.lock()));
STDIN_SOURCE = get_stdin_source
}
get_stdin_source()
}
#[inline(always)]
fn get_stdin_source() -> &'static mut StdinLock<'static> { unsafe { STDIN.as_mut().unwrap() } }
static mut INPUT: FastInput = FastInput::new();
static mut STDIN: *mut StdinLock<'static> = 0 as *mut StdinLock<'static>;
static mut STDIN_SOURCE: fn() -> &'static mut StdinLock<'static> = init;
pub fn get_input() -> &'static mut FastInput { unsafe { &mut INPUT } }
pub fn set_interactive() { unsafe { INPUT.set_interactive() } }
}
pub use input::{get_input, set_interactive};
#[macro_export]
macro_rules! __cargo_equip_macro_def_iolib_scan {
// Terminator
( $(, )? ) => {};
// Vec<Vec<....>>, ......
( $v: ident : [ [ $( $inner:tt )+ ] ; $len:expr ] $(, $( $rest:tt )* )? ) => {
let $v = (0..$len).map(|_| { $crate::__cargo_equip::crates::iolib::scan!(w: [ $( $inner )+ ]); w }).collect::<Vec<_>>();
$( $crate::__cargo_equip::crates::iolib::scan!($( $rest )*); )?
};
// Vec<$t>, .....
( $v:ident : [ $t:tt ; $len:expr ] $(, $( $rest:tt )* )? ) => {
let $v = (0..$len).map(|_| { $crate::__cargo_equip::crates::iolib::scan!($v : $t); $v }).collect::<Vec<_>>();
$( $crate::__cargo_equip::crates::iolib::scan!($( $rest )*); )?
};
// Expand tuple
( @expandtuple, ( $t:tt )) => {
{ $crate::__cargo_equip::crates::iolib::scan!(w: $t); w }
};
// Expand tuple
( @expandtuple, ( $t:tt $(, $rest:tt )* ) ) => {
(
$crate::__cargo_equip::crates::iolib::scan!(@expandtuple, ( $t ))
$(, $crate::__cargo_equip::crates::iolib::scan!(@expandtuple, ( $rest )) )*
)
};
// let $v: ($t, $u, ....) = (.......)
( $v:ident : ( $( $rest:tt )* ) ) => {
let $v = $crate::__cargo_equip::crates::iolib::scan!(@expandtuple, ( $( $rest )* ));
};
// let $v: $t = ......, .......
( $v:ident : $t:tt $(, $( $rest:tt )* )? ) => {
$crate::__cargo_equip::crates::iolib::read_value!($v : $t);
$( $crate::__cargo_equip::crates::iolib::scan!($( $rest )*); )?
};
// ......
( $( $rest:tt )* ) => {
$crate::__cargo_equip::crates::iolib::scan!($( $rest )*);
};
}
macro_rules! scan {
($($tt:tt)*) => (crate::__cargo_equip_macro_def_iolib_scan!{$($tt)*});
}
#[macro_export]
macro_rules! __cargo_equip_macro_def_iolib_scani {
( $( $rest:tt )* ) => {
$crate::__cargo_equip::crates::iolib::set_interactive();
$crate::__cargo_equip::crates::iolib::scan!( $( $rest )* );
};
}
macro_rules! scani {
($($tt:tt)*) => (crate::__cargo_equip_macro_def_iolib_scani!{$($tt)*});
}
#[macro_export]
macro_rules! __cargo_equip_macro_def_iolib_read_value {
( $v:ident : i8 ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_i8();
};
( $v:ident : i16 ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_i16();
};
( $v:ident : i32 ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_i32();
};
( $v:ident : i64 ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_i64();
};
( $v:ident : i128 ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_i128();
};
( $v:ident : isize ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_isize();
};
( $v:ident : u8 ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_u8();
};
( $v:ident : u16 ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_u16();
};
( $v:ident : u32 ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_u32();
};
( $v:ident : u64 ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_u64();
};
( $v:ident : u128 ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_u128();
};
( $v:ident : usize ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_usize();
};
( $v:ident : char ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_char();
};
( $v:ident : String ) => {
let $v = $crate::__cargo_equip::crates::iolib::get_input().read_string();
};
( $v:ident : $t:ty ) => {
let $v: $t = $crate::__cargo_equip::crates::iolib::get_input()
.read_string()
.parse()
.unwrap();
};
}
macro_rules! read_value {
($($tt:tt)*) => (crate::__cargo_equip_macro_def_iolib_read_value!{$($tt)*});
}
}
pub mod math {
use crate::__cargo_equip::preludes::math::*;
use numeric::Integer;
//////////////////////////////////////////////////////////////////////////////////
// Define famous functions for integers
//////////////////////////////////////////////////////////////////////////////////
/// Return gcd(x, y).
#[inline]
pub fn gcd<T: Integer>(mut x: T, mut y: T) -> T {
while y != T::zero() {
let (nx, ny) = (y, x % y);
x = nx;
y = ny;
}
x
}
/// Return lcm(x, y).
#[inline]
pub fn lcm<T: Integer>(x: T, y: T) -> T { x / gcd(x, y) * y }
/// Solve the equation "ax + by = gcd(a, b)"
/// Return (gcd(a, b), x, y)
// s * 1 + t * 0 = s ...(1) (sx = 1, sy = 0)
// s * 0 + t * 1 = t ...(2) (tx = 0, ty = 1)
// -> (1) - (2) * |s/t|
// -> s * (sx - tx * |s/t|) + t * (sy - ty * |s/t|) = s % t
// Repeating this, the right-hand side becomes gcd(s, t)
// s * tx + t * ty = gcd(s, t)
#[inline]
pub fn ext_gcd<T: Integer>(a: T, b: T) -> (T, T, T) {
let (mut s, mut t) = (a, b);
let (mut sx, mut tx) = (T::one(), T::zero());
let (mut sy, mut ty) = (T::zero(), T::one());
while s % t != T::zero() {
let d = s / t;
let u = s % t;
let ux = sx - tx * d;
let uy = sy - ty * d;
s = t;
sx = tx;
sy = ty;
t = u;
tx = ux;
ty = uy;
}
(t, tx, ty)
}
/// Using p as the modulus, calculate a^n.
#[inline]
pub fn mod_pow(a: i64, mut n: i64, p: i64) -> i64 {
let mut res = 1;
let mut pow = a;
while n != 0 {
if n & 1 != 0 {
res = (res as i128 * pow as i128 % p as i128) as i64;
}
pow = (pow as i128 * pow as i128 % p as i128) as i64;
n >>= 1;
}
res
}
/// Return an integer x less than lcm(m1, m2) satisfying x = a (mod m1) and x = b (mod m2) and lcm(m1, m2).
/// If no integers satisfy the condition, return None.
// m1 = gcd(m1, m2) * p, m2 = gcd(m1, m2) * q
// -> x = a (mod gcd(m1, m2)) && x = b (mod gcd(m1, m2))
// m1 * k + m2 * l = gcd(m1, m2) = d
// -> now, * s (= (b - a) / d)
// s * m1 * k + s * m2 * l = b - a
// -> a + s * m1 * k = b - s * m2 * l = x
// -> x = a (mod m1) && x = b (mod m2)
#[inline]
pub fn chinese_remainder_theorem(mut a: i64, mut m1: i64, mut b: i64, mut m2: i64) -> Option<(i64, i64)> {
if m1 < m2 {
std::mem::swap(&mut a, &mut b);
std::mem::swap(&mut m1, &mut m2);
}
let (a, b) = (a.rem_euclid(m1), b.rem_euclid(m2));
if m1 % m2 == 0 {
return if a % m2 != b { None } else { Some((a, m1)) };
}
let (d, k, _) = ext_gcd(m1, m2);
let u1 = m2 / d;
if a % d != b % d {
return None;
}
let x = (b - a) / d % u1 * k % u1;
let m = m1 * u1;
let res = (a + x * m1).rem_euclid(m);
Some((res, m))
}
/// Return a minimum integer x (mod modulo) satisfying x = a[i] (mod p[i]) for any i and p[1]*p[2]*p[3].... (mod modulo)
/// Note: For any i, j (i != j), gcd(p[i], p[j]) MUST be 1.
// x = t1 + t2p1 + t3p1p2 + t4p1p2p3 + ...
// x = a1 (mod p1)
// -> a1 = x % p1 = t1 (mod p1)
// x = a2 (mod p2)
// -> a2 = x % p2 = t1 + t2p1 (mod p2)
// -> t2 = (a2 - t1) * p1^{-1} (mod p2)
// ... so, t[k] = ((...((a[k] - t[1])p[1,k]^{-1} - t[2])p[2,k]^{-1} - ...)p[k-2,k]^{-1} - t[k-1]))p[k-1,k]^{-1} (mod p[k])
// = a[k]p[1,k]^{-1}p[2,k]^{-1}...p[k-1,k]^{-1} - t[1]p[1,k]^{-1}p[2,k]^{-1}...p[k-1,k]^{-1} - t[2]p[2,k]^{-1}p[3,k]^{-1}...p[k-1,k]^{-1} - ... - t[k-1]p[k-1,k]^{-1}
// = a[k](p[1,k]p[2,k]...p[k-1,k])^{-1} - t[1](p[1,k]p[2,k]...p[k-1,k])^{-1} - t[2](p[2,k]p[3,k]...p[k-1,k])^{-1} - ... - t[k-1]p[k-1,k]^{-1}
// = (a[k] - x[..k]) * (p[1,k]p[2,k]p[3,k]...p[k-1,k])^{-1}
// = (a[k] - res[k]) * prod[k]^{-1}
#[inline]
pub fn garner(a: &[i64], p: &[i64], modulo: i64) -> (i64, i64) {
assert_eq!(a.len(), p.len());
// prod[i] = p[0]p[1]...p[i-1]
// res[i] = t[0] + t[1]p[0] + t[2]p[0]p[1] + ... t[i-1]p[0]p[1]...p[i-2]
let mut prod = vec![1; p.len() + 1];
let mut res = vec![0; p.len() + 1];
for (i, (&a, &m)) in a.iter().zip(p.iter()).enumerate() {
let a = a % m;
let (_, inv, _) = ext_gcd(prod[i], m);
let t = ((a - res[i]) * inv).rem_euclid(m);
for (i, &p) in p.iter().enumerate().skip(i + 1) {
res[i] = (res[i] + (t * prod[i])) % p;
prod[i] = (prod[i] * m) % p;
}
res[p.len()] = (res[p.len()] + (t * prod[p.len()])) % modulo;
prod[p.len()] = (prod[p.len()] * m) % modulo;
}
(res[p.len()], prod[p.len()])
}
/// Return a minimum integer x (mod modulo) satisfying x = a[i] (mod p[i]) for any i and p[1]*p[2]*p[3].... (mod modulo)
/// For any i, j (i != j), gcd(p[i], p[j]) = 1 is not required.
/// If the condition is inconsistent and no solution exists, return None.
#[inline]
pub fn garner_prechecked(a: &[i64], p: &[i64], modulo: i64) -> Option<(i64, i64)> {
let mut p = p.to_vec();
for i in 0..a.len() {
for j in 0..i {
let mut g = gcd(p[i], p[j]);
if (a[i] - a[j]) % g != 0 {
return None;
}
p[i] /= g;
p[j] /= g;
let mut gi = gcd(p[i], g);
let mut gj = g / gi;
g = gcd(gi, gj);
gi *= g;
gj /= g;
while g != 1 {
g = gcd(gi, gj);
gi *= g;
gj /= g;
}
p[i] *= gi;
p[j] *= gj;
}
}
Some(garner(a, &p, modulo))
}
}
pub mod numeric {
pub mod float {
use super::Numeric;
use std::ops::Neg;
macro_rules! impl_numeric_trait_for_float {
( $( $t:tt )* ) => {
$(impl Numeric for $t {
fn max_value() -> Self { std::$t::MAX }
fn min_value() -> Self { std::$t::MIN }
})*
};
}
impl_numeric_trait_for_float!(f32 f64);
pub trait Float: Numeric + Neg<Output = Self> {
fn abs(self) -> Self;
fn acos(self) -> Self;
fn asin(self) -> Self;
fn atan(self) -> Self;
fn atan2(self, other: Self) -> Self;
fn cbrt(self) -> Self;
fn ceil(self) -> Self;
fn cos(self) -> Self;
fn div_euclid(self, rhs: Self) -> Self;
fn floor(self) -> Self;
fn hypot(self, other: Self) -> Self;
fn is_finite(self) -> bool;
fn is_infinite(self) -> bool;
fn is_nan(self) -> bool;
fn is_sign_negative(self) -> bool;
fn is_sign_positive(self) -> bool;
fn max(self, other: Self) -> Self;
fn min(self, other: Self) -> Self;
fn mul_add(self, a: Self, b: Self) -> Self;
fn powf(self, n: Self) -> Self;
fn powi(self, n: i32) -> Self;
fn rem_euclid(self, rhs: Self) -> Self;
fn round(self) -> Self;
fn signum(self) -> Self;
fn sin(self) -> Self;
fn sin_cos(self) -> (Self, Self);
fn sqrt(self) -> Self;
fn tan(self) -> Self;
fn to_radians(self) -> Self;
fn pi() -> Self;
}
macro_rules! impl_float_trait {
( $( $t:tt )* ) => {
$(impl Float for $t {
fn abs(self) -> Self { self.abs() }
fn acos(self) -> Self { self.acos() }
fn asin(self) -> Self { self.asin() }
fn atan(self) -> Self { self.atan() }
fn atan2(self, other: Self) -> Self { self.atan2(other) }
fn cbrt(self) -> Self { self.cbrt() }
fn ceil(self) -> Self { self.ceil() }
fn cos(self) -> Self { self.cos() }
fn div_euclid(self, rhs: Self) -> Self { self.div_euclid(rhs) }
fn floor(self) -> Self { self.floor() }
fn hypot(self, other: Self) -> Self { self.hypot(other) }
fn is_finite(self) -> bool { self.is_finite() }
fn is_infinite(self) -> bool { self.is_infinite() }
fn is_nan(self) -> bool { self.is_nan() }
fn is_sign_negative(self) -> bool { self.is_sign_negative() }
fn is_sign_positive(self) -> bool { self.is_sign_positive() }
fn max(self, other: Self) -> Self { self.max(other) }
fn min(self, other: Self) -> Self { self.min(other) }
fn mul_add(self, a: Self, b: Self) -> Self { self.mul_add(a, b) }
fn powf(self, n: Self) -> Self { self.powf(n) }
fn powi(self, n: i32) -> Self { self.powi(n) }
fn rem_euclid(self, rhs: Self) -> Self { self.rem_euclid(rhs) }
fn round(self) -> Self { self.round() }
fn signum(self) -> Self { self.signum() }
fn sin(self) -> Self { self.sin() }
fn sin_cos(self) -> (Self, Self) { self.sin_cos() }
fn sqrt(self) -> Self { self.sqrt() }
fn tan(self) -> Self { self.tan() }
fn to_radians(self) -> Self { self.to_radians() }
fn pi() -> Self { std::$t::consts::PI }
})*
};
}
impl_float_trait!(f32 f64);
}
pub mod integer {
use super::Numeric;
use std::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign};
macro_rules! impl_numeric_trait_for_integer {
( $( $t:tt )* ) => {
$(impl Numeric for $t {
fn max_value() -> Self { std::$t::MAX }
fn min_value() -> Self { std::$t::MIN }
})*
};
}
impl_numeric_trait_for_integer!(i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize);
pub trait Integer:
Numeric
+ Rem<Self, Output = Self>
+ RemAssign
+ Shl<i32, Output = Self>
+ Shl<i64, Output = Self>
+ Shl<u32, Output = Self>
+ Shl<u64, Output = Self>
+ Shl<usize, Output = Self>
+ Shr<i32, Output = Self>
+ Shr<i64, Output = Self>
+ Shr<u32, Output = Self>
+ Shr<u64, Output = Self>
+ Shr<usize, Output = Self>
+ ShlAssign<i32>
+ ShlAssign<i64>
+ ShlAssign<u32>
+ ShlAssign<u64>
+ ShlAssign<usize>
+ ShrAssign<i32>
+ ShrAssign<i64>
+ ShrAssign<u32>
+ ShrAssign<u64>
+ ShrAssign<usize>
+ BitAnd<Self, Output = Self>
+ BitOr<Self, Output = Self>
+ BitXor<Self, Output = Self>
+ BitAndAssign
+ BitOrAssign
+ BitXorAssign
+ std::hash::Hash
+ Eq
+ Ord
{
fn abs_diff(self, other: Self) -> Self;
fn count_ones(self) -> u32;
fn count_zeros(self) -> u32;
fn div_euclid(self, rhs: Self) -> Self;
fn leading_ones(self) -> u32;
fn leading_zeros(self) -> u32;
fn rem_euclid(self, rhs: Self) -> Self;
fn reverse_bits(self) -> Self;
fn rotate_left(self, n: u32) -> Self;
fn rotate_right(self, n: u32) -> Self;
fn trailing_ones(self) -> u32;
fn trailing_zeros(self) -> u32;
fn overflowing_add(self, rhs: Self) -> (Self, bool);
fn overflowing_mul(self, rhs: Self) -> (Self, bool);
fn overflowing_neg(self) -> (Self, bool);
fn overflowing_shl(self, rhs: u32) -> (Self, bool);
fn overflowing_shr(self, rhs: u32) -> (Self, bool);
fn overflowing_sub(self, rhs: Self) -> (Self, bool);
fn saturating_add(self, rhs: Self) -> Self;
fn saturating_mul(self, rhs: Self) -> Self;
fn saturating_sub(self, rhs: Self) -> Self;
fn wrapping_add(self, rhs: Self) -> Self;
fn wrapping_mul(self, rhs: Self) -> Self;
fn wrapping_neg(self) -> Self;
fn wrapping_shl(self, rhs: u32) -> Self;
fn wrapping_shr(self, rhs: u32) -> Self;
fn wrapping_sub(self, rhs: Self) -> Self;
}
macro_rules! impl_integer_trait {
( $( $t:ty )* ) => {
$(impl Integer for $t {
fn abs_diff(self, other: Self) -> Self { std::cmp::max(self, other) - std::cmp::min(self, other) }
fn count_ones(self) -> u32 { self.count_ones() }
fn count_zeros(self) -> u32 { self.count_zeros() }
fn div_euclid(self, rhs: Self) -> Self { self.div_euclid(rhs) }
fn leading_ones(self) -> u32 { (!self).leading_zeros() }
fn leading_zeros(self) -> u32 { self.leading_zeros() }
fn rem_euclid(self, rhs: Self) -> Self { self.rem_euclid(rhs) }
fn reverse_bits(self) -> Self { self.reverse_bits() }
fn rotate_left(self, n: u32) -> Self { self.rotate_left(n) }
fn rotate_right(self, n: u32) -> Self { self.rotate_right(n) }
fn trailing_ones(self) -> u32 { (!self).trailing_zeros() }
fn trailing_zeros(self) -> u32 { self.trailing_zeros() }
fn overflowing_add(self, rhs: Self) -> (Self, bool) { self.overflowing_add(rhs) }
fn overflowing_mul(self, rhs: Self) -> (Self, bool) { self.overflowing_mul(rhs) }
fn overflowing_neg(self) -> (Self, bool) { self.overflowing_neg() }
fn overflowing_shl(self, rhs: u32) -> (Self, bool) { self.overflowing_shl(rhs) }
fn overflowing_shr(self, rhs: u32) -> (Self, bool) { self.overflowing_shr(rhs) }
fn overflowing_sub(self, rhs: Self) -> (Self, bool) { self.overflowing_sub(rhs) }
fn saturating_add(self, rhs: Self) -> Self { self.saturating_add(rhs) }
fn saturating_mul(self, rhs: Self) -> Self { self.saturating_mul(rhs) }
fn saturating_sub(self, rhs: Self) -> Self { self.saturating_sub(rhs) }
fn wrapping_add(self, rhs: Self) -> Self { self.wrapping_add(rhs) }
fn wrapping_mul(self, rhs: Self) -> Self { self.wrapping_mul(rhs) }
fn wrapping_neg(self) -> Self { self.wrapping_neg() }
fn wrapping_shl(self, rhs: u32) -> Self { self.wrapping_shl(rhs) }
fn wrapping_shr(self, rhs: u32) -> Self { self.wrapping_shr(rhs) }
fn wrapping_sub(self, rhs: Self) -> Self { self.wrapping_sub(rhs) }
})*
};
}
impl_integer_trait!(i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize);
}
pub mod one {
pub trait One {
fn one() -> Self;
}
macro_rules! impl_one_integer {
( $( $t:ty )* ) => {
$(impl One for $t {
fn one() -> $t { 1 }
})*
};
}
impl_one_integer!(i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize);
macro_rules! impl_one_float {
( $( $t:ty )* ) => {
$(impl One for $t {
fn one() -> $t { 1.0 }
})*
};
}
impl_one_float!(f32 f64);
}
pub mod signed {
use std::ops::Neg;
pub trait Signed: Neg<Output = Self> + std::marker::Sized {
fn is_negative(self) -> bool;
fn is_positive(self) -> bool;
}
macro_rules! impl_integer_trait {
( $( $t:ty )* ) => {
$(impl Signed for $t {
fn is_negative(self) -> bool {
self.is_negative()
}
fn is_positive(self) -> bool {
self.is_positive()
}
})*
};
}
impl_integer_trait!(i8 i16 i32 i64 i128 isize);
}
pub mod zero {
pub trait Zero {
fn zero() -> Self;
}
macro_rules! impl_zero_integer {
( $( $t:ty )* ) => {
$(impl Zero for $t {
fn zero() -> $t { 0 }
})*
};
}
impl_zero_integer!(i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize);
macro_rules! impl_zero_float {
( $( $t:ty )* ) => {
$(impl Zero for $t {
fn zero() -> $t { 0.0 }
})*
};
}
impl_zero_float!(f32 f64);
}
pub use float::Float;
pub use integer::Integer;
pub use one::One;
pub use signed::Signed;
pub use zero::Zero;
use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};
#[derive(Debug)]
pub struct Error(pub &'static str);
impl std::fmt::Display for Error {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}", self.0) }
}
impl std::error::Error for Error {}
pub trait UnorderedNumeric:
Add<Self, Output = Self>
+ Sub<Self, Output = Self>
+ Mul<Self, Output = Self>
+ Div<Self, Output = Self>
+ AddAssign
+ SubAssign
+ MulAssign
+ DivAssign
+ std::fmt::Debug
+ std::fmt::Display
+ Clone
+ Copy
+ PartialEq
+ Default
+ Zero
+ One
{
}
pub trait Numeric:
Add<Self, Output = Self>
+ Sub<Self, Output = Self>
+ Mul<Self, Output = Self>
+ Div<Self, Output = Self>
+ AddAssign
+ SubAssign
+ MulAssign
+ DivAssign
+ std::fmt::Debug
+ std::fmt::Display
+ Clone
+ Copy
+ PartialEq
+ PartialOrd
+ Default
+ Zero
+ One
{
fn max_value() -> Self;
fn min_value() -> Self;
}
pub trait IntoFloat: Numeric {
fn as_f64(self) -> f64;
fn as_f32(self) -> f32;
}
impl IntoFloat for i64 {
fn as_f64(self) -> f64 { self as f64 }
fn as_f32(self) -> f32 { self as f32 }
}
}
}
pub(crate) mod macros {
pub mod iolib {
pub use crate::{
__cargo_equip_macro_def_iolib_read_value as read_value, __cargo_equip_macro_def_iolib_scan as scan, __cargo_equip_macro_def_iolib_scani as scani,
};
}
pub mod math {}
pub mod modint {}
pub mod numeric {}
}
pub(crate) mod prelude {
pub use crate::__cargo_equip::crates::*;
}
mod preludes {
pub mod iolib {}
pub mod math {
pub(in crate::__cargo_equip) use crate::__cargo_equip::crates::numeric;
}
pub mod modint {
pub(in crate::__cargo_equip) use crate::__cargo_equip::crates::numeric;
}
pub mod numeric {}
}
}