Submission #41063134
Source Code Expand
// -*- coding:utf-8-unix -*-
// rustup doc --std --toolchain 1.42.0
#![allow(unused_imports)]
pub fn solve<I: fastproconio::NextToken>(input: &mut I) {
// Initialize.
use fastproconio::*;
#[rustfmt::skip] #[cfg(tcheck)] let tins = std::time::Instant::now();
#[rustfmt::skip] #[cfg(tcheck)] let mut durs = Vec::with_capacity(16);
#[rustfmt::skip] #[allow(unused_macros)] macro_rules! finput {($($r:tt)*)=>{finput_inner!{input,$($r)*}};}
#[rustfmt::skip] #[allow(unused_macros)] macro_rules! fread {($t:tt)=>{{fread_value!(input,$t)}};}
let mut obuf = ProconWriteBuffer::with_capacity(1 << 26);
let mut out = std::io::stdout();
//let mut out = std::io::BufWriter::with_capacity(out.lock(), 1 << 26);
//let err = std::io::stderr();
//let mut err = std::io::BufWriter::with_capacity(err.lock(), 1 << 26);
#[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "initialize"));
// Input. (Only some or no input if you want to input in parallel with the main process.)
finput! {
n: u64,
}
#[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "input"));
// Main Process, Output.
let er = Eratosthenes::generate_v6((n / 12).sqrt());
let primes = er.vec_primes_u32();
#[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "er"));
let mut count = 0;
let amax = n.nth_root(5) as u32;
for (i, &a) in primes.iter().enumerate() {
if a >= amax {
break;
}
let bmax_cube = n / u64::from(a).pow(2);
let bmax = bmax_cube.cbrt() as u32;
let jmax = match primes.binary_search(&bmax) {
Ok(j) => j,
Err(j) => j.saturating_sub(1),
};
for (j, &b) in primes[..=jmax].iter().enumerate().skip(i + 1) {
let k = match primes.binary_search(&((bmax_cube / u64::from(b)).sqrt() as u32))
{
Ok(k) => k,
Err(k) => k.saturating_sub(1),
};
if j < k {
count += k - j;
} else {
break;
}
}
}
obuf.usize(count);
obuf.lf();
obuf.write_all(&mut out);
//std::io::Write::flush(&mut out).ok();
#[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "output"));
// Execution Time.
#[rustfmt::skip] #[cfg(tcheck)] for (dur, s) in durs.iter() { eprintln!("{:.6} {}", dur.as_secs_f64(), s); };
}
use bitset_fixed::BitSet;
use itertools::*;
use num::integer::*;
use petgraph::algo::*;
use petgraph::graph::{DiGraph, Graph, NodeIndex, UnGraph};
use petgraph::unionfind::UnionFind;
use petgraph::visit::{
Bfs, Dfs, EdgeRef, IntoEdges, NodeCount, NodeIndexable, VisitMap, Visitable,
};
//use proconio::{input, marker::{Bytes, Chars, Isize1, Usize1}, source::{auto::AutoSource, line::LineSource, once::OnceSource}};
use rand::prelude::*;
use regex::Regex;
use rustc_hash::{FxHashMap, FxHashSet, FxHasher};
use std::{
collections::*,
convert::{TryFrom, TryInto},
hash::BuildHasherDefault,
io::{stderr, stdin, stdout, BufRead, BufReader, BufWriter, Read, Write},
iter::FromIterator,
};
use superslice::Ext;
#[allow(unused_macros)]
#[macro_export]
macro_rules! invariant {
($expr: expr) => {
debug_assert!($expr);
if !($expr) {
#[allow(unused_unsafe)]
unsafe {
core::hint::unreachable_unchecked()
};
}
};
}
/// chmax, chmin sugar syntax
trait Change {
fn chmax(&mut self, x: Self);
fn chmin(&mut self, x: Self);
}
impl<T: PartialOrd> Change for T {
fn chmax(&mut self, x: T) {
if *self < x {
*self = x;
}
}
fn chmin(&mut self, x: T) {
if *self > x {
*self = x;
}
}
}
pub mod fastproconio {
use crate::invariant;
use std::convert::{Into, TryInto};
/// input macros based on tanakh's input macro / proconio-rs.
/// tanakh's input macro: <https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8>
/// proconio-rs: <https://docs.rs/proconio/0.3.8/proconio/>
/// ProconIBufIter receive `std::io::BufRead` trait. (`std::io::StdinLock`, `std::io::BufReader`, `&[u8]`, etc.)
#[macro_export]
macro_rules! finput_inner {
($source:expr) => {};
($source:expr, ) => {};
($source:expr, mut $var:ident : $t:tt $($r:tt)*) => {
let mut $var = fread_value!($source, $t);
finput_inner!{$source $($r)*}
};
($source:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = fread_value!($source, $t);
finput_inner!{$source $($r)*}
};
}
#[macro_export]
macro_rules! fread_value {
($source:expr, ( $($t:tt),* )) => { ( $(fread_value!($source, $t)),* ) };
($source:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| fread_value!($source, $t)).collect::<Vec<_>>() };
($source:expr, u128) => { $source.next_wordtoken().as_slice().parse_u128_raw() };
($source:expr, usize) => { $source.next_wordtoken().as_slice().parse_u64_raw() as usize };
($source:expr, usize1) => { $source.next_wordtoken().as_slice().parse_u64_raw() as usize - 1 };
($source:expr, u64) => { $source.next_wordtoken().as_slice().parse_u64_raw() };
($source:expr, u64_1) => { $source.next_wordtoken().as_slice().parse_u64_raw() - 1 };
($source:expr, u32) => { $source.next_wordtoken().as_slice().parse_u32_raw() };
($source:expr, u32_1) => { $source.next_wordtoken().as_slice().parse_u32_raw() - 1 };
($source:expr, u16) => { $source.next_wordtoken().as_slice().parse_u16_raw() };
($source:expr, u16_1) => { $source.next_wordtoken().as_slice().parse_u16_raw() - 1 };
($source:expr, u8) => { $source.next_wordtoken().as_slice().parse_u8_raw() };
($source:expr, i128) => { $source.next_wordtoken().as_slice().parse_i128_raw() };
($source:expr, isize) => { $source.next_wordtoken().as_slice().parse_i64_raw() as isize };
($source:expr, i64) => { $source.next_wordtoken().as_slice().parse_i64_raw() };
($source:expr, i32) => { $source.next_wordtoken().as_slice().parse_i32_raw() };
($source:expr, i16) => { $source.next_wordtoken().as_slice().parse_i16_raw() };
($source:expr, i8) => { $source.next_wordtoken().as_slice().parse_i8_raw() };
($source:expr, byte) => { $source.get_ascii_byte() };
($source:expr, Bytes) => {{ $source.next_wordtoken().as_vec() }};
($source:expr, BytesToken) => {{ $source.next_wordtoken() }};
($source:expr, String) => {unsafe { $source.next_wordtoken().as_string_unchecked() }};
($source:expr, LineBytes) => {{ $source.next_linetoken().as_vec() }};
($source:expr, LineBytesToken) => {{ $source.next_linetoken() }};
($source:expr, LineString) => {unsafe { $source.next_linetoken().as_string_unchecked() }};
($source:expr, $t:ty) => {{ unsafe { String::from_utf8_unchecked($source.next_wordtoken().as_slice()) }.parse::<$t>().expect("Parse error") }};
}
unsafe fn ptr_offset_u8(dist: *const u8, origin: *const u8) -> usize {
// Rust 1.47.0 or later, `dist.offset_from(origin) as usize`
// <https://doc.rust-lang.org/std/primitive.pointer.html#method.offset_from>
dist as usize - origin as usize
}
#[derive(Clone, Debug)]
pub enum Token<'a /* ' */> {
Slice(&'a /* ' */ [u8]),
Bytes(Vec<u8>),
}
impl Token<'_ /* ' */> {
pub fn as_slice(&self) -> &[u8] {
match self {
Self::Slice(s) => s,
Self::Bytes(v) => v.as_slice(),
}
}
pub fn as_vec(self) -> Vec<u8> {
match self {
Self::Slice(s) => s.to_vec(),
Self::Bytes(v) => v,
}
}
pub fn as_string(self) -> Result<String, std::string::FromUtf8Error> {
String::from_utf8(self.as_vec())
}
pub unsafe fn as_string_unchecked(self) -> String {
String::from_utf8_unchecked(self.as_vec())
}
}
pub trait NextToken {
fn get_ascii_byte(&mut self) -> u8;
fn next_wordtoken(&mut self) -> Token;
fn next_linetoken(&mut self) -> Token;
}
pub struct BytesIter<'a /* ' */>(pub &'a /* ' */ [u8]);
impl NextToken for BytesIter<'_ /* ' */> {
fn get_ascii_byte(&mut self) -> u8 {
while let [first, remain @ ..] = self.0 {
self.0 = remain;
if *first >= 0x21 {
return *first;
}
}
panic!()
}
fn next_wordtoken(&mut self) -> Token {
while let [first, remain @ ..] = self.0 {
if *first < 0x21 {
self.0 = remain;
} else {
break;
}
}
let mut split2 = self.0.splitn(2, |&c| c < 0x21);
let cur = split2.next().unwrap_or(b"");
self.0 = split2.next().unwrap_or(b"");
Token::Slice(cur)
}
fn next_linetoken(&mut self) -> Token {
while let [first, remain @ ..] = self.0 {
if *first < 0x21 {
self.0 = remain;
} else {
break;
}
}
let mut split2 = self.0.splitn(2, |&c| c == b'\n');
let mut cur = split2.next().unwrap_or(b"");
while let [remain @ .., last] = cur {
if *last < 0x21 {
cur = remain;
} else {
break;
}
}
self.0 = split2.next().unwrap_or(b"");
Token::Slice(cur)
}
}
/// Interaction with `std::io::BufRead` Trait, Implementation of `Iterator<Item = u8>`
pub struct ProconIBufIter<R: std::io::BufRead> {
inner: R,
raw: *const u8,
ptr: *const u8,
end: *const u8,
len: usize,
balign: *const u8,
wmask: Vec<u64>,
}
impl<R: std::io::BufRead> ProconIBufIter<R> {
pub fn new(inner: R) -> Self {
const EMPTY_U8_SLICE: &'static /* ' */ [u8] = b"";
Self {
inner,
raw: EMPTY_U8_SLICE.as_ptr(),
ptr: EMPTY_U8_SLICE.as_ptr(),
end: EMPTY_U8_SLICE.as_ptr(),
len: 0,
balign: EMPTY_U8_SLICE.as_ptr(),
wmask: vec![0u64; 200],
}
}
}
impl<R: std::io::BufRead> ProconIBufIter<R> {
pub fn buf_empty(&self) -> bool {
self.ptr == self.end
}
#[allow(clippy::missing_safety_doc)]
#[cold]
unsafe fn inner_read(&mut self) -> bool {
invariant!(self.ptr == self.end);
self.inner.consume(ptr_offset_u8(self.ptr, self.raw));
if let Ok(s) = self.inner.fill_buf() {
self.raw = s.as_ptr();
self.ptr = s.as_ptr();
self.end = s.as_ptr().add(s.len());
self.len = s.len();
self.balign = (self.raw as usize & !0x3f) as *const u8;
let alignlen = (((self.end as usize) + 0x3f) & (!0x3f)) - self.balign as usize;
let wmasklen = (alignlen + 63) / 64;
#[cfg(target_arch = "x86_64")]
{
#[target_feature(enable = "avx2")]
unsafe fn genmask_avx2(asl: &[u8], bsl: &mut [u64]) {
use std::arch::x86_64::*;
let diff = _mm256_set1_epi8(-0x21);
for (a, b) in asl.chunks_exact(64).zip(bsl.iter_mut()) {
let s0 = _mm256_load_si256(std::mem::transmute(a.as_ptr().add(0)));
let s1 = _mm256_load_si256(std::mem::transmute(a.as_ptr().add(32)));
let a0 = _mm256_add_epi8(s0, diff);
let a1 = _mm256_add_epi8(s1, diff);
let m0 = _mm256_movemask_epi8(_mm256_andnot_si256(s0, a0)) as u32;
let m1 = _mm256_movemask_epi8(_mm256_andnot_si256(s1, a1)) as u32;
*b = ((m1 as u64) << 32) | (m0 as u64);
}
}
unsafe fn genmask_sse2(asl: &[u8], bsl: &mut [u64]) {
use std::arch::x86_64::*;
let diff = _mm_set1_epi8(-0x21);
for (a, b) in asl.chunks_exact(64).zip(bsl.iter_mut()) {
let s0 = _mm_load_si128(std::mem::transmute(a.as_ptr().add(0)));
let s1 = _mm_load_si128(std::mem::transmute(a.as_ptr().add(16)));
let s2 = _mm_load_si128(std::mem::transmute(a.as_ptr().add(32)));
let s3 = _mm_load_si128(std::mem::transmute(a.as_ptr().add(48)));
let a0 = _mm_add_epi8(s0, diff);
let a1 = _mm_add_epi8(s1, diff);
let a2 = _mm_add_epi8(s2, diff);
let a3 = _mm_add_epi8(s3, diff);
let m0 = _mm_movemask_epi8(_mm_andnot_si128(s0, a0)) as u16;
let m1 = _mm_movemask_epi8(_mm_andnot_si128(s1, a1)) as u16;
let m2 = _mm_movemask_epi8(_mm_andnot_si128(s2, a2)) as u16;
let m3 = _mm_movemask_epi8(_mm_andnot_si128(s3, a3)) as u16;
*b = ((m3 as u64) << 48)
| ((m2 as u64) << 32)
| ((m1 as u64) << 16)
| (m0 as u64);
}
}
if self.wmask.len() <= wmasklen {
self.wmask
.extend(std::iter::repeat(0).take(wmasklen + 1 - self.wmask.len()));
}
let asl = std::slice::from_raw_parts(self.balign, wmasklen * 64);
if is_x86_feature_detected!("avx2") {
genmask_avx2(asl, &mut self.wmask);
} else {
genmask_sse2(asl, &mut self.wmask);
}
};
self.len != 0
} else {
self.raw = self.ptr;
self.len = self.end as usize - self.ptr as usize;
false
}
}
#[allow(clippy::missing_safety_doc)]
unsafe fn next_unchecked(&mut self) -> u8 {
let p = self.ptr;
self.ptr = p.add(1);
*p
}
/// skip unmatch bytes
pub fn skipuntil_bytes_fn<F: FnMut(u8) -> bool>(&mut self, f: &mut F) -> bool {
loop {
let mut ptr = self.ptr;
while ptr != self.end {
if f(unsafe { *ptr }) {
self.ptr = ptr;
return true;
}
unsafe {
ptr = ptr.add(1);
}
}
self.ptr = ptr;
if unsafe { !self.inner_read() } {
return false;
}
}
}
pub fn get_ascii_bytes(&mut self, vec: &mut Vec<u8>) {
if !self.skipuntil_bytes_fn(&mut |c: u8| c > b' ') {
return;
}
#[cfg(target_arch = "x86_64")]
unsafe {
let ptr = self.ptr;
let pdiff = (self.ptr as usize) - (self.balign as usize) + 1;
let (p64q, p64r) = (pdiff / 64, pdiff % 64);
let mut w = self.wmask.as_ptr().add(p64q);
let wmask = (*w) & ((!0u64) << p64r);
let mut p = self.balign.add(p64q * 64);
if wmask != 0 {
p = p.add(wmask.trailing_zeros() as usize);
if p < self.end {
self.ptr = p.add(1);
vec.extend_from_slice(std::slice::from_raw_parts(
ptr,
p as usize - ptr as usize,
));
return;
}
}
p = p.add(64);
w = w.add(1);
let end64 = self.end.sub(64);
while p < end64 {
let wmask = *w;
if wmask != 0 {
let tlz = wmask.trailing_zeros();
let pp = p.add(tlz as usize);
self.ptr = pp.add(1);
vec.extend_from_slice(std::slice::from_raw_parts(
ptr,
pp as usize - ptr as usize,
));
return;
}
p = p.add(64);
w = w.add(1);
}
if p < self.end {
let wmask = *w;
if wmask != 0 {
let tlz = wmask.trailing_zeros();
let pp = p.add(tlz as usize);
if pp < self.end {
self.ptr = pp.add(1);
vec.extend_from_slice(std::slice::from_raw_parts(
ptr,
pp as usize - ptr as usize,
));
return;
}
}
}
vec.extend_from_slice(std::slice::from_raw_parts(
ptr,
self.end as usize - ptr as usize,
));
loop {
self.ptr = self.end;
if !self.inner_read() {
return;
}
let ptr = self.ptr;
let pdiff = (ptr as usize) - (self.balign as usize);
let (p64q, p64r) = (pdiff / 64, pdiff % 64);
let mut w = self.wmask.as_ptr().add(p64q);
let mut wmask = (*w) & ((!0u64) << p64r);
let mut p = self.balign.add(p64q * 64);
while p < self.end {
if wmask != 0 {
p = p.add(wmask.trailing_zeros() as usize);
if p < self.end {
self.ptr = p.add(1);
vec.extend_from_slice(std::slice::from_raw_parts(
ptr,
p as usize - ptr as usize,
));
return;
}
break;
}
p = p.add(64);
w = w.add(1);
wmask = *w;
}
vec.extend_from_slice(std::slice::from_raw_parts(
ptr,
self.end as usize - ptr as usize,
));
}
}
#[cfg(not(target_arch = "x86_64"))]
unsafe {
let ptr = self.ptr;
let mut p = ptr.add(1);
while p < self.end {
if *p <= b' ' {
self.ptr = p.add(1);
vec.extend_from_slice(std::slice::from_raw_parts(
ptr,
p as usize - ptr as usize,
));
return;
}
p = p.add(1);
}
vec.extend_from_slice(std::slice::from_raw_parts(
ptr,
self.end as usize - ptr as usize,
));
loop {
self.ptr = self.end;
if !self.inner_read() {
break;
}
let ptr = self.ptr;
let mut p = ptr;
while p < self.end {
if *p <= b' ' {
self.ptr = p.add(1);
vec.extend_from_slice(std::slice::from_raw_parts(
ptr,
p as usize - ptr as usize,
));
return;
}
p = p.add(1);
}
vec.extend_from_slice(std::slice::from_raw_parts(
ptr,
self.end as usize - ptr as usize,
));
}
return;
}
}
}
impl<R: std::io::BufRead> NextToken for ProconIBufIter<R> {
fn get_ascii_byte(&mut self) -> u8 {
self.get_ascii_byte_opt().unwrap()
}
#[inline]
fn next_wordtoken(&mut self) -> Token {
if !self.skipuntil_bytes_fn(&mut |c: u8| c > b' ') {
return Token::Slice(b"");
}
#[cfg(target_arch = "x86_64")]
unsafe {
let ptr = self.ptr;
let pdiff = (self.ptr as usize) - (self.balign as usize) + 1;
let (p64q, p64r) = (pdiff / 64, pdiff % 64);
let mut w = self.wmask.as_ptr().add(p64q);
let wmask = (*w) & ((!0u64) << p64r);
let mut p = self.balign.add(p64q * 64);
if wmask != 0 {
p = p.add(wmask.trailing_zeros() as usize);
if p < self.end {
self.ptr = p.add(1);
return Token::Slice(std::slice::from_raw_parts(
ptr,
p as usize - ptr as usize,
));
}
}
p = p.add(64);
w = w.add(1);
let end64 = self.end.sub(64);
while p < end64 {
let wmask = *w;
if wmask != 0 {
let tlz = wmask.trailing_zeros();
let pp = p.add(tlz as usize);
self.ptr = pp.add(1);
return Token::Slice(std::slice::from_raw_parts(
ptr,
pp as usize - ptr as usize,
));
}
p = p.add(64);
w = w.add(1);
}
if p < self.end {
let wmask = *w;
if wmask != 0 {
let tlz = wmask.trailing_zeros();
let pp = p.add(tlz as usize);
if pp < self.end {
self.ptr = pp.add(1);
return Token::Slice(std::slice::from_raw_parts(
ptr,
pp as usize - ptr as usize,
));
}
}
}
let mut v =
std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize).to_vec();
loop {
self.ptr = self.end;
if !self.inner_read() {
return Token::Bytes(v);
}
let ptr = self.ptr;
let pdiff = (ptr as usize) - (self.balign as usize);
let (p64q, p64r) = (pdiff / 64, pdiff % 64);
let mut w = self.wmask.as_ptr().add(p64q);
let mut wmask = (*w) & ((!0u64) << p64r);
let mut p = self.balign.add(p64q * 64);
while p < self.end {
if wmask != 0 {
p = p.add(wmask.trailing_zeros() as usize);
if p < self.end {
self.ptr = p.add(1);
v.extend_from_slice(std::slice::from_raw_parts(
ptr,
p as usize - ptr as usize,
));
return Token::Bytes(v);
}
break;
}
p = p.add(64);
w = w.add(1);
wmask = *w;
}
v.extend_from_slice(std::slice::from_raw_parts(
ptr,
self.end as usize - ptr as usize,
));
}
}
#[cfg(not(target_arch = "x86_64"))]
unsafe {
let ptr = self.ptr;
let mut p = ptr.add(1);
while p < self.end {
if *p <= b' ' {
self.ptr = p.add(1);
return Token::Slice(std::slice::from_raw_parts(
ptr,
p as usize - ptr as usize,
));
}
p = p.add(1);
}
let mut v =
std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize).to_vec();
loop {
self.ptr = self.end;
if !self.inner_read() {
break;
}
let ptr = self.ptr;
let mut p = ptr;
while p < self.end {
if *p <= b' ' {
self.ptr = p.add(1);
v.extend_from_slice(std::slice::from_raw_parts(
ptr,
p as usize - ptr as usize,
));
return Token::Bytes(v);
}
p = p.add(1);
}
v.extend_from_slice(std::slice::from_raw_parts(
ptr,
self.end as usize - ptr as usize,
));
}
return Token::Bytes(v);
}
}
#[inline]
fn next_linetoken(&mut self) -> Token {
if !self.skipuntil_bytes_fn(&mut |c: u8| c >= b' ') {
return Token::Slice(b"");
}
#[cfg(target_arch = "x86_64")]
unsafe {
let ptr = self.ptr;
let pdiff = (self.ptr as usize) - (self.balign as usize) + 1;
let (p64q, p64r) = (pdiff / 64, pdiff % 64);
let mut w = self.wmask.as_ptr().add(p64q);
let mut wmask = (*w) & ((!0u64) << p64r);
let mut p = self.balign.add(p64q * 64);
's: /* ' */ while p < self.end {
while wmask != 0 {
let tlz = wmask.trailing_zeros();
let pp = p.add(tlz as usize);
if pp >= self.end {
break 's; /* ' */
}
if *pp < b' ' {
self.ptr = pp.add(1);
return Token::Slice(std::slice::from_raw_parts(
ptr,
pp as usize - ptr as usize,
));
}
wmask &= wmask.wrapping_sub(1); // elase least one bit
}
p = p.add(64);
w = w.add(1);
wmask = *w;
}
let mut v =
std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize).to_vec();
loop {
self.ptr = self.end;
if !self.inner_read() {
break;
}
let ptr = self.ptr;
let pdiff = (ptr as usize) - (self.balign as usize);
let (p64q, p64r) = (pdiff / 64, pdiff % 64);
let mut w = self.wmask.as_ptr().add(p64q);
let mut wmask = (*self.wmask.get_unchecked(p64q)) & ((!0u64) << p64r);
let mut p = self.balign.add(p64q * 64);
'v: /* ' */ while p < self.end {
while wmask != 0 {
let tlz = wmask.trailing_zeros();
let pp = p.add(tlz as usize);
if pp >= self.end {
break 'v; /* ' */
}
assert!(*pp < b' ');
if (*pp) < b' ' {
self.ptr = pp.add(1);
v.extend_from_slice(std::slice::from_raw_parts(
ptr,
pp as usize - ptr as usize,
));
return Token::Bytes(v);
}
wmask &= wmask.wrapping_sub(1); // elase least one bit
}
p = p.add(64);
w = w.add(1);
wmask = *w;
}
v.extend_from_slice(std::slice::from_raw_parts(
ptr,
self.end as usize - ptr as usize,
));
}
return Token::Bytes(v);
}
#[cfg(not(target_arch = "x86_64"))]
unsafe {
let ptr = self.ptr;
let mut p = ptr.add(1);
while p < self.end {
if *p < b' ' {
self.ptr = p.add(1);
return Token::Slice(std::slice::from_raw_parts(
ptr,
p as usize - ptr as usize,
));
}
p = p.add(1);
}
let mut v =
std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize).to_vec();
loop {
self.ptr = self.end;
if !self.inner_read() {
break;
}
let ptr = self.ptr;
let mut p = ptr;
while p < self.end {
if *p < b' ' {
self.ptr = p.add(1);
v.extend_from_slice(std::slice::from_raw_parts(
ptr,
p as usize - ptr as usize,
));
return Token::Bytes(v);
}
p = p.add(1);
}
v.extend_from_slice(std::slice::from_raw_parts(
ptr,
self.end as usize - ptr as usize,
));
}
return Token::Bytes(v);
}
}
}
impl<R: std::io::BufRead> Iterator for ProconIBufIter<R> {
type Item = u8;
fn next(&mut self) -> Option<Self::Item> {
if !self.buf_empty() || unsafe { self.inner_read() } {
Some(unsafe { self.next_unchecked() })
} else {
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(usize::max_value(), None)
}
}
pub trait UPrimInt:
Copy
+ Default
+ std::cmp::Ord
+ std::ops::Add<Output = Self>
+ std::ops::Sub<Output = Self>
+ std::ops::Mul<Output = Self>
+ std::ops::Div<Output = Self>
+ std::ops::Rem<Output = Self>
+ std::ops::AddAssign
+ std::ops::SubAssign
+ std::ops::MulAssign
+ std::ops::DivAssign
+ std::ops::RemAssign
+ std::ops::Shl<u32, Output = Self>
+ std::ops::Shr<u32, Output = Self>
+ std::ops::ShlAssign<u32>
+ std::ops::ShrAssign<u32>
+ std::ops::BitAnd<Output = Self>
+ std::ops::BitOr<Output = Self>
+ std::ops::BitXor<Output = Self>
+ std::ops::BitAndAssign
+ std::ops::BitOrAssign
+ std::ops::BitXorAssign
+ std::convert::From<u8>
{
const BITS: u32;
fn count_zeros(self) -> u32;
fn trailing_zeros(self) -> u32;
fn leading_zeros(self) -> u32;
}
macro_rules! impl_uprimint {
($t:ty) => {
impl UPrimInt for $t {
const BITS: u32 = (0 as $t).count_zeros();
fn count_zeros(self) -> u32 {
self.count_zeros()
}
fn trailing_zeros(self) -> u32 {
self.trailing_zeros()
}
fn leading_zeros(self) -> u32 {
self.leading_zeros()
}
}
};
}
impl_uprimint!(u8);
impl_uprimint!(u16);
impl_uprimint!(u32);
impl_uprimint!(u64);
impl_uprimint!(u128);
impl_uprimint!(usize);
pub trait IPrimInt:
Copy
+ Default
+ std::cmp::Ord
+ std::ops::Add<Output = Self>
+ std::ops::Sub<Output = Self>
+ std::ops::Neg<Output = Self>
+ std::ops::Mul<Output = Self>
+ std::ops::Div<Output = Self>
+ std::ops::Rem<Output = Self>
+ std::convert::From<i8>
{
const BITS: u32;
}
macro_rules! impl_iprimint {
($t:ty) => {
impl IPrimInt for $t {
const BITS: u32 = (0 as $t).count_zeros();
}
};
}
impl_iprimint!(i8);
impl_iprimint!(i16);
impl_iprimint!(i32);
impl_iprimint!(i64);
impl_iprimint!(i128);
impl_iprimint!(isize);
#[inline]
fn parseuint_arith8le(mut a: u64) -> u64 {
a = (a & 0x0f0f0f0f0f0f0f0f).wrapping_mul((10 << 8) + 1) >> 8;
a = (a & 0x00ff00ff00ff00ff).wrapping_mul((100 << 16) + 1) >> 16;
(a & 0x0000ffff0000ffff).wrapping_mul((10000 << 32) + 1) >> 32
}
#[inline]
#[allow(unused)]
fn parseuint_arith8be(mut a: u64) -> u64 {
a = (a & 0x0f0f0f0f0f0f0f0f).wrapping_mul((1 << 8) + 10) >> 8;
a = (a & 0x00ff00ff00ff00ff).wrapping_mul((1 << 16) + 100) >> 16;
(a & 0x0000ffff0000ffff).wrapping_mul((1 << 32) + 10000) >> 32
}
#[inline]
fn parseuint_arith4le(mut a: u32) -> u32 {
a = (a & 0x0f0f0f0f).wrapping_mul((10 << 8) + 1) >> 8;
(a & 0x00ff00ff).wrapping_mul((100 << 16) + 1) >> 16
}
#[inline]
#[allow(unused)]
fn parseuint_arith4be(mut a: u32) -> u32 {
a = (a & 0x0f0f0f0f).wrapping_mul((1 << 8) + 10) >> 8;
(a & 0x00ff00ff).wrapping_mul((1 << 16) + 100) >> 16
}
#[inline]
fn parseuint_arith2le(a: u16) -> u16 {
(a & 0x0f0f).wrapping_mul((10 << 8) + 1) >> 8
}
#[inline]
#[allow(unused)]
fn parseuint_arith2be(a: u16) -> u16 {
(a & 0x0f0f).wrapping_mul((1 << 8) + 10) >> 8
}
#[inline(always)]
#[allow(unused)]
fn parseuint_arith1(a: u8) -> u8 {
a & 0x0f
}
#[inline(always)]
fn parseuint_raw32b(s: [u8; 32]) -> u128 {
let a = parseuint_arith8le(u64::from_le_bytes(s[0..8].try_into().unwrap()));
let b = parseuint_arith8le(u64::from_le_bytes(s[8..16].try_into().unwrap()));
let c = parseuint_arith8le(u64::from_le_bytes(s[16..24].try_into().unwrap()));
let d = parseuint_arith8le(u64::from_le_bytes(s[24..32].try_into().unwrap()));
((a * 100000000 + b) as u128) * 10000000000000000 + ((c * 100000000 + d) as u128)
}
#[inline(always)]
fn parseuint_raw16b(s: [u8; 16]) -> u64 {
let a = parseuint_arith8le(u64::from_le_bytes(s[0..8].try_into().unwrap()));
let b = parseuint_arith8le(u64::from_le_bytes(s[8..16].try_into().unwrap()));
a * 100000000 + b
}
#[inline(always)]
fn parseuint_raw8b(s: [u8; 8]) -> u64 {
parseuint_arith8le(u64::from_le_bytes(s))
}
#[rustfmt::skip]
#[inline(always)]
fn parseuint_raw7b(s: &[u8]) -> u64 {
invariant!(s.len() <= 8);
match s.len() {
0 => 0,
1 => parseuint_arith1(s[0]) as u64,
2 => parseuint_arith2le(u16::from_le_bytes(s[0..2].try_into().unwrap())) as u64,
3 => parseuint_arith4le(((s[0] as u32) << 8) | ((u16::from_le_bytes(s[1..3].try_into().unwrap()) as u32) << 16)) as u64,
4 => parseuint_arith4le(u32::from_le_bytes(s[0..4].try_into().unwrap())) as u64,
5 => parseuint_arith8le(((s[0] as u64) << 24) | ((u32::from_le_bytes(s[1..5].try_into().unwrap()) as u64) << 32)),
6 => parseuint_arith8le(((u16::from_le_bytes(s[0..2].try_into().unwrap()) as u64) << 16) | ((u32::from_le_bytes(s[2..6].try_into().unwrap()) as u64) << 32)),
7 => parseuint_arith8le(((u32::from_le_bytes(s[0..4].try_into().unwrap()) as u64) << 8) | ((u32::from_le_bytes(s[3..7].try_into().unwrap()) as u64) << 32)),
_ => parseuint_arith8le(u64::from_le_bytes(s[0..8].try_into().unwrap())),
}
}
#[inline(always)]
fn parseuint_raw4b(s: [u8; 4]) -> u32 {
parseuint_arith4le(u32::from_le_bytes(s))
}
#[rustfmt::skip]
#[inline(always)]
fn parseuint_raw3b(s: &[u8]) -> u32 {
invariant!(s.len() <= 4);
match s.len() {
0 => 0,
1 => parseuint_arith1(s[0]) as u32,
2 => parseuint_arith2le(u16::from_le_bytes(s[0..2].try_into().unwrap())) as u32,
3 => parseuint_arith4le(((s[0] as u32) << 8) | ((u16::from_le_bytes(s[1..3].try_into().unwrap()) as u32) << 16)),
_ => parseuint_arith4le(u32::from_le_bytes(s[0..4].try_into().unwrap())),
}
}
#[inline(always)]
fn parseuint_raw2b(s: [u8; 2]) -> u16 {
parseuint_arith2le(u16::from_le_bytes(s))
}
#[inline(always)]
fn parseuint_raw1b(s: u8) -> u8 {
parseuint_arith1(s)
}
pub trait ByteParseIntRaw {
fn parse_u128_raw(&self) -> u128;
fn parse_u64_raw(&self) -> u64;
fn parse_u32_raw(&self) -> u32;
fn parse_u16_raw(&self) -> u16;
fn parse_u8_raw(&self) -> u8;
fn parse_i128_raw(&self) -> i128;
fn parse_i64_raw(&self) -> i64;
fn parse_i32_raw(&self) -> i32;
fn parse_i16_raw(&self) -> i16;
fn parse_i8_raw(&self) -> i8;
fn parse_u128_rawopt(&self) -> Option<u128>;
fn parse_u64_rawopt(&self) -> Option<u64>;
fn parse_u32_rawopt(&self) -> Option<u32>;
fn parse_u16_rawopt(&self) -> Option<u16>;
fn parse_u8_rawopt(&self) -> Option<u8>;
}
impl ByteParseIntRaw for &[u8] {
// parse_u128_raw: empty or int(self) > u128::MAX or self.len() > 39 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
#[rustfmt::skip]
#[inline(always)]
fn parse_u128_raw(&self) -> u128 {
invariant!(!self.is_empty());
invariant!(self.len() <= 39);
invariant!(self.iter().all(u8::is_ascii_digit));
match self.len() {
0 => 0,
1 => parseuint_raw1b(self[0]) as u128,
2 => parseuint_raw2b(self[0..2].try_into().unwrap()) as u128,
3 => parseuint_arith4le(((self[0] as u32) << 8) | ((u16::from_le_bytes(self[1..3].try_into().unwrap()) as u32) << 16)) as u128,
4 => parseuint_raw4b(self[0..4].try_into().unwrap()) as u128,
5 => parseuint_arith8le(((self[0] as u64) << 24) | ((u32::from_le_bytes(self[1..5].try_into().unwrap()) as u64) << 32)) as u128,
6 => parseuint_arith8le(((u16::from_le_bytes(self[0..2].try_into().unwrap()) as u64) << 16) | ((u32::from_le_bytes(self[2..6].try_into().unwrap()) as u64) << 32)) as u128,
7 => parseuint_arith8le(((u32::from_le_bytes(self[0..4].try_into().unwrap()) as u64) << 8) | ((u32::from_le_bytes(self[3..7].try_into().unwrap()) as u64) << 32)) as u128,
8 => parseuint_raw8b(self[0..8].try_into().unwrap()) as u128,
9 => ((parseuint_raw1b(self[0]) as u64) * 1_0000_0000 + parseuint_raw8b(self[1..9].try_into().unwrap())) as u128,
10 => ((parseuint_raw2b(self[0..2].try_into().unwrap()) as u64) * 1_0000_0000 + parseuint_raw8b(self[2..10].try_into().unwrap())) as u128,
11 => ((parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap()) << 8) as u64) * 1_0000_0000 + parseuint_raw8b(self[3..11].try_into().unwrap())) as u128,
12 => ((parseuint_raw4b(self[0..4].try_into().unwrap()) as u64) * 1_0000_0000 + parseuint_raw8b(self[4..12].try_into().unwrap())) as u128,
13 => (parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap()) << 24) * 1_0000_0000 + parseuint_raw8b(self[5..13].try_into().unwrap())) as u128,
14 => (parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap()) << 16) * 1_0000_0000 + parseuint_raw8b(self[6..14].try_into().unwrap())) as u128,
15 => (parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap()) << 8) * 1_0000_0000 + parseuint_raw8b(self[7..15].try_into().unwrap())) as u128,
16 => parseuint_raw16b(self[0..16].try_into().unwrap()) as u128,
17 => ((parseuint_raw1b(self[0]) as u64) * 1_0000_0000_0000_0000 + parseuint_raw16b(self[1..17].try_into().unwrap())) as u128,
18 => ((parseuint_raw2b(self[0..2].try_into().unwrap()) as u64) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[2..18].try_into().unwrap()))) as u128,
19 => ((parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap()) << 8) as u64) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[3..19].try_into().unwrap()))) as u128,
20 => (parseuint_raw4b(self[0..4].try_into().unwrap()) as u128) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[4..20].try_into().unwrap()) as u128),
21 => (parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap()) << 24) as u128) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[5..21].try_into().unwrap()) as u128),
22 => (parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap()) << 16) as u128) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[6..22].try_into().unwrap()) as u128),
23 => (parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap()) << 8) as u128) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[7..23].try_into().unwrap()) as u128),
24 => (parseuint_raw8b(self[0..8].try_into().unwrap()) as u128) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[8..24].try_into().unwrap()) as u128),
25 => (((parseuint_raw1b(self[0]) as u64) * 1_0000_0000 + parseuint_raw8b(self[1..9].try_into().unwrap())) as u128) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[9..25].try_into().unwrap()) as u128),
26 => (((parseuint_raw2b(self[0..2].try_into().unwrap()) as u64) * 1_0000_0000 + parseuint_raw8b(self[2..10].try_into().unwrap())) as u128) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[10..26].try_into().unwrap()) as u128),
27 => (((parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap()) << 8) as u64) * 1_0000_0000 + parseuint_raw8b(self[3..11].try_into().unwrap())) as u128) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[11..27].try_into().unwrap()) as u128),
28 => (((parseuint_raw4b(self[0..4].try_into().unwrap()) as u64) * 1_0000_0000 + parseuint_raw8b(self[4..12].try_into().unwrap())) as u128) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[12..28].try_into().unwrap()) as u128),
29 => (((parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap()) << 24) as u64) * 1_0000_0000 + parseuint_raw8b(self[5..13].try_into().unwrap())) as u128) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[13..29].try_into().unwrap()) as u128),
30 => (((parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap()) << 16) as u64) * 1_0000_0000 + parseuint_raw8b(self[6..14].try_into().unwrap())) as u128) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[14..30].try_into().unwrap()) as u128),
31 => (((parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap()) << 8) as u64) * 1_0000_0000 + parseuint_raw8b(self[7..15].try_into().unwrap())) as u128) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[15..31].try_into().unwrap()) as u128),
32 => parseuint_raw32b(self[0..32].try_into().unwrap()),
33 => parseuint_raw32b(self[0..32].try_into().unwrap()) * 10 + (parseuint_raw1b(self[32]) as u128),
34 => parseuint_raw32b(self[0..32].try_into().unwrap()) * 100 + (parseuint_raw2b(self[32..34].try_into().unwrap()) as u128),
35 => parseuint_raw32b(self[0..32].try_into().unwrap()) * 1000 + (parseuint_arith4le(u32::from_le_bytes(self[31..35].try_into().unwrap()) & 0x00000000_0f0f0f00) as u128),
36 => parseuint_raw32b(self[0..32].try_into().unwrap()) * 1_0000 + (parseuint_raw4b(self[32..36].try_into().unwrap()) as u128),
37 => parseuint_raw32b(self[0..32].try_into().unwrap()) * 10_0000 + (parseuint_arith8le(u64::from_le_bytes(self[29..37].try_into().unwrap()) & 0x0f0f0f0f_0f000000) as u128),
38 => parseuint_raw32b(self[0..32].try_into().unwrap()) * 100_0000 + (parseuint_arith8le(u64::from_le_bytes(self[30..38].try_into().unwrap()) & 0x0f0f0f0f_0f0f0000) as u128),
_ => parseuint_raw32b(self[0..32].try_into().unwrap()) * 1000_0000 + (parseuint_arith8le(u64::from_le_bytes(self[31..39].try_into().unwrap()) & 0x0f0f0f0f_0f0f0f00) as u128),
}
}
// parse_u64_raw: empty or int(self) > u64::MAX or self.len() > 20 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
#[rustfmt::skip]
#[inline(always)]
fn parse_u64_raw(&self) -> u64 {
invariant!(!self.is_empty());
invariant!(self.len() <= 20);
invariant!(self.iter().all(u8::is_ascii_digit));
match self.len() {
0 => 0,
1 => parseuint_arith1(self[0]) as u64,
2 => parseuint_arith2le(u16::from_le_bytes(self[0..2].try_into().unwrap())) as u64,
3 => parseuint_arith4le(((self[0] as u32) << 8) | ((u16::from_le_bytes(self[1..3].try_into().unwrap()) as u32) << 16)) as u64,
4 => parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())) as u64,
5 => parseuint_arith8le(((self[0] as u64) << 24) | ((u32::from_le_bytes(self[1..5].try_into().unwrap()) as u64) << 32)),
6 => parseuint_arith8le(((u16::from_le_bytes(self[0..2].try_into().unwrap()) as u64) << 16) | ((u32::from_le_bytes(self[2..6].try_into().unwrap()) as u64) << 32)),
7 => parseuint_arith8le(((u32::from_le_bytes(self[0..4].try_into().unwrap()) as u64) << 8) | ((u32::from_le_bytes(self[3..7].try_into().unwrap()) as u64) << 32)),
8 => parseuint_raw8b(self[0..8].try_into().unwrap()),
9 => (parseuint_arith1(self[0]) as u64) * 1_0000_0000 + parseuint_raw8b(self[1..9].try_into().unwrap()),
10 => (parseuint_arith2le(u16::from_le_bytes(self[0..2].try_into().unwrap())) as u64) * 1_0000_0000 + parseuint_raw8b(self[2..10].try_into().unwrap()),
11 => (parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap()) << 8) as u64) * 1_0000_0000 + parseuint_raw8b(self[3..11].try_into().unwrap()),
12 => (parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())) as u64) * 1_0000_0000 + parseuint_raw8b(self[4..12].try_into().unwrap()),
13 => parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap()) << 24) * 1_0000_0000 + parseuint_raw8b(self[5..13].try_into().unwrap()),
14 => parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap()) << 16) * 1_0000_0000 + parseuint_raw8b(self[6..14].try_into().unwrap()),
15 => parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap()) << 8) * 1_0000_0000 + parseuint_raw8b(self[7..15].try_into().unwrap()),
16 => parseuint_raw16b(self[0..16].try_into().unwrap()),
17 => (parseuint_arith1(self[0]) as u64) * 1_0000_0000_0000_0000 + parseuint_raw16b(self[1..17].try_into().unwrap()),
18 => (parseuint_arith2le(u16::from_le_bytes(self[0..2].try_into().unwrap())) as u64) * 1_0000_0000_0000_0000 + parseuint_raw16b(self[2..18].try_into().unwrap()),
19 => (parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap()) << 8) as u64) * 1_0000_0000_0000_0000 + parseuint_raw16b(self[3..19].try_into().unwrap()),
_ => (parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())) as u64) * 1_0000_0000_0000_0000 + (parseuint_raw16b(self[4..20].try_into().unwrap())),
}
}
// parse_u32_raw: empty or int(self) > u32::MAX or self.len() > 10 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
#[rustfmt::skip]
#[inline(always)]
fn parse_u32_raw(&self) -> u32 {
invariant!(!self.is_empty());
invariant!(self.len() <= 10);
invariant!(self.iter().all(u8::is_ascii_digit));
match self.len() {
0 => 0,
1 => parseuint_arith1(self[0]) as u32,
2 => parseuint_arith2le(u16::from_le_bytes(self[0..2].try_into().unwrap())) as u32,
3 => parseuint_arith4le(((self[0] as u32) << 8) | ((u16::from_le_bytes(self[1..3].try_into().unwrap()) as u32) << 16)),
4 => parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())),
5 => parseuint_arith8le(((self[0] as u64) << 24) | ((u32::from_le_bytes(self[1..5].try_into().unwrap()) as u64) << 32)) as u32,
6 => parseuint_arith8le(((u16::from_le_bytes(self[0..2].try_into().unwrap()) as u64) << 16) | ((u32::from_le_bytes(self[2..6].try_into().unwrap()) as u64) << 32)) as u32,
7 => parseuint_arith8le(((u32::from_le_bytes(self[0..4].try_into().unwrap()) as u64) << 8) | ((u32::from_le_bytes(self[3..7].try_into().unwrap()) as u64) << 32)) as u32,
8 => parseuint_raw8b(self[0..8].try_into().unwrap()) as u32,
9 => (parseuint_arith1(self[0]) as u32) * 1_0000_0000 + parseuint_raw8b(self[1..9].try_into().unwrap()) as u32,
_ => (parseuint_arith2le(u16::from_le_bytes(self[0..2].try_into().unwrap())) as u32) * 1_0000_0000 + (parseuint_raw8b(self[2..10].try_into().unwrap()) as u32),
}
}
// parse_u16_raw: empty or int(self) > u16::MAX or self.len() > 5 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
#[inline(always)]
fn parse_u16_raw(&self) -> u16 {
invariant!(!self.is_empty());
invariant!(self.len() <= 5);
invariant!(self.iter().all(u8::is_ascii_digit));
parseuint_raw7b(&self) as u16
}
// parse_u8_raw: empty or int(self) > u8::MAX or self.len() > 3 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
#[inline(always)]
fn parse_u8_raw(&self) -> u8 {
invariant!(!self.is_empty());
invariant!(self.len() <= 3);
invariant!(self.iter().all(u8::is_ascii_digit));
parseuint_raw3b(&self) as u8
}
#[inline(always)]
fn parse_i128_raw(&self) -> i128 {
invariant!(!self.is_empty());
if self.is_empty() {
0
} else if self[0] == b'-' {
(&self[1..]).parse_u128_raw().wrapping_neg() as i128
} else {
self.parse_u128_raw() as i128
}
}
#[inline(always)]
fn parse_i64_raw(&self) -> i64 {
invariant!(!self.is_empty());
if self.is_empty() {
0
} else if self[0] == b'-' {
(&self[1..]).parse_u64_raw().wrapping_neg() as i64
} else {
self.parse_u64_raw() as i64
}
}
#[inline(always)]
fn parse_i32_raw(&self) -> i32 {
invariant!(!self.is_empty());
if self.is_empty() {
0
} else if self[0] == b'-' {
(&self[1..]).parse_u32_raw().wrapping_neg() as i32
} else {
self.parse_u32_raw() as i32
}
}
#[inline(always)]
fn parse_i16_raw(&self) -> i16 {
invariant!(!self.is_empty());
if self.is_empty() {
0
} else if self[0] == b'-' {
(&self[1..]).parse_u16_raw().wrapping_neg() as i16
} else {
self.parse_u16_raw() as i16
}
}
#[inline(always)]
fn parse_i8_raw(&self) -> i8 {
invariant!(!self.is_empty());
if self.is_empty() {
0
} else if self[0] == b'-' {
(&self[1..]).parse_u128_raw().wrapping_neg() as i8
} else {
self.parse_u128_raw() as i8
}
}
// parse_u128_rawopt: empty or int(self) > u128::MAX or self.len() > 39 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
fn parse_u128_rawopt(&self) -> Option<u128> {
invariant!(!self.is_empty());
invariant!(self.len() <= 39);
invariant!(self.iter().all(u8::is_ascii_digit));
let (s15, s16) = self.split_at(self.len() % 16);
let r = match s15.len() / 4 {
0 => s15.iter().fold(0, |p, &c| p * 10 + ((c & 0x0f) as u64)),
1 => {
if self.len() < 4 {
unsafe { core::hint::unreachable_unchecked() }
}
s15[4..].iter().fold(
parseuint_raw4b(s15[0..4].try_into().unwrap()) as u64,
|p, &c| p * 10 + ((c & 0x0f) as u64),
)
}
2 => {
if self.len() < 8 {
unsafe { core::hint::unreachable_unchecked() }
}
s15[8..]
.iter()
.fold(parseuint_raw8b(s15[0..8].try_into().unwrap()), |p, &c| {
p * 10 + ((c & 0x0f) as u64)
})
}
_ => {
if self.len() < 12 {
unsafe { core::hint::unreachable_unchecked() }
}
s15[12..].iter().fold(
parseuint_raw8b(s15[0..8].try_into().unwrap()) * 10000
+ parseuint_raw4b(s15[8..12].try_into().unwrap()) as u64,
|p, &c| p * 10 + ((c & 0x0f) as u64),
)
}
};
match s16.len() {
0 => Some(r as u128),
16 => Some(
(r as u128) * 10000000000000000
+ parseuint_raw16b(s16.try_into().unwrap()) as u128,
),
32 => (r as u128)
.checked_mul(100000000000000000000000000000000)?
.checked_add(parseuint_raw32b(s16.try_into().unwrap())),
_ => None,
}
}
// parse_u64_rawopt: empty or int(self) > u64::MAX or self.len() > 20 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
fn parse_u64_rawopt(&self) -> Option<u64> {
invariant!(!self.is_empty());
invariant!(self.len() <= 20);
invariant!(self.iter().all(u8::is_ascii_digit));
match self.len() / 4 {
0 => Some(self.iter().fold(0, |p, &c| p * 10 + ((c & 0x0f) as u64))),
1 => {
if self.len() < 4 {
unsafe { core::hint::unreachable_unchecked() }
}
Some(self[4..].iter().fold(
parseuint_raw4b(self[0..4].try_into().unwrap()) as u64,
|p, &c| p * 10 + ((c & 0x0f) as u64),
))
}
2 => {
if self.len() < 8 {
unsafe { core::hint::unreachable_unchecked() }
}
Some(
self[8..]
.iter()
.fold(parseuint_raw8b(self[0..8].try_into().unwrap()), |p, &c| {
p * 10 + ((c & 0x0f) as u64)
}),
)
}
3 => {
if self.len() < 12 {
unsafe { core::hint::unreachable_unchecked() }
}
Some(self[12..].iter().fold(
parseuint_raw8b(self[0..8].try_into().unwrap()) * 10000
+ parseuint_raw4b(self[8..12].try_into().unwrap()) as u64,
|p, &c| p * 10 + ((c & 0x0f) as u64),
))
}
4 => {
if self.len() < 16 {
unsafe { core::hint::unreachable_unchecked() }
}
Some(self[16..].iter().fold(
parseuint_raw16b(self[0..16].try_into().unwrap()),
|p, &c| p * 10 + ((c & 0x0f) as u64),
))
}
5 => {
if self.len() < 20 {
unsafe { core::hint::unreachable_unchecked() }
}
self[20..].iter().fold(
parseuint_raw16b(self[0..16].try_into().unwrap())
.checked_mul(10000)?
.checked_add(parseuint_raw4b(self[16..20].try_into().unwrap()) as u64),
|p, &c| p?.checked_mul(10)?.checked_add((c & 0x0f) as u64),
)
}
_ => None,
}
}
// parse_u32_rawopt: empty or int(self) > u32::MAX or self.len() > 10 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
fn parse_u32_rawopt(&self) -> Option<u32> {
invariant!(!self.is_empty());
invariant!(self.len() <= 10);
invariant!(self.iter().all(u8::is_ascii_digit));
match self.len() / 4 {
0 => Some(self.iter().fold(0, |p, &c| p * 10 + ((c & 0x0f) as u32))),
1 => {
if self.len() < 4 {
unsafe { core::hint::unreachable_unchecked() }
}
Some(self[4..].iter().fold(
parseuint_raw4b(self[0..4].try_into().unwrap()) as u32,
|p, &c| p * 10 + ((c & 0x0f) as u32),
))
}
2 => {
if self.len() < 8 {
unsafe { core::hint::unreachable_unchecked() }
}
self[8..].iter().fold(
Some(parseuint_raw8b(self[0..8].try_into().unwrap()) as u32),
|p, &c| p?.checked_mul(10)?.checked_add((c & 0x0f) as u32),
)
}
_ => None,
}
}
// parse_u16_rawopt: empty or int(self) > u16::MAX or self.len() > 5 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
fn parse_u16_rawopt(&self) -> Option<u16> {
invariant!(!self.is_empty());
invariant!(self.len() <= 5);
invariant!(self.iter().all(u8::is_ascii_digit));
match self.len() / 4 {
0 => Some(self.iter().fold(0, |p, &c| p * 10 + ((c & 0x0f) as u16))),
1 => {
if self.len() < 4 {
unsafe { core::hint::unreachable_unchecked() }
}
self[4..].iter().fold(
Some(parseuint_raw4b(self[0..4].try_into().unwrap()) as u16),
|p, &c| p?.checked_mul(10)?.checked_add((c & 0x0f) as u16),
)
}
_ => None,
}
}
// parse_u8_rawopt: empty or int(self) > u8::MAX or self.len() > 3 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
fn parse_u8_rawopt(&self) -> Option<u8> {
invariant!(!self.is_empty());
invariant!(self.len() <= 3);
invariant!(self.iter().all(u8::is_ascii_digit));
match self.len() {
0..=2 => Some(self.iter().fold(0, |p, &c| p * 10 + (c & 0x0f))),
3 => ((self[0] & 0x0f) * 10 + (self[1] & 0x0f))
.checked_mul(10)?
.checked_add(self[2] & 0x0f),
_ => None,
}
}
}
/// speed frenzy input parser for program compete
pub trait ProconParse {
fn get_ascii_byte_or_default(&mut self) -> u8 {
self.get_ascii_byte_opt().unwrap_or_default()
}
fn get_ascii_byte_opt(&mut self) -> Option<u8>;
fn parse_uint<U: UPrimInt>(&mut self) -> U {
self.parse_uint_opt().unwrap()
}
fn parse_uint_or_default<U: UPrimInt>(&mut self) -> U {
self.parse_uint_opt().unwrap_or_default()
}
fn parse_uint_opt<U: UPrimInt>(&mut self) -> Option<U>;
fn parse_iint<I: IPrimInt>(&mut self) -> I {
self.parse_iint_opt().unwrap()
}
fn parse_iint_or_default<I: IPrimInt>(&mut self) -> I {
self.parse_iint_opt().unwrap_or_default()
}
fn parse_iint_opt<I: IPrimInt>(&mut self) -> Option<I>;
}
impl<T: Iterator<Item = u8>> ProconParse for T {
fn get_ascii_byte_opt(&mut self) -> Option<u8> {
loop {
match self.next() {
Some(c @ 0x21..=0x7e) => {
return Some(c);
}
Some(_) => continue,
_ => return None,
}
}
}
fn parse_uint_opt<U: UPrimInt>(&mut self) -> Option<U> {
loop {
match self.next() {
Some(c @ b'0'..=b'9') => {
let mut v = U::from(c - b'0');
while let Some(c @ b'0'..=b'9') = self.next() {
v = v * U::from(10) + U::from(c - b'0');
}
return Some(v);
}
Some(_) => continue,
_ => return None,
}
}
}
fn parse_iint_opt<I: IPrimInt>(&mut self) -> Option<I> {
loop {
match self.next() {
Some(c @ b'0'..=b'9') => {
let mut v = I::from((c - b'0') as i8);
while let Some(c @ b'0'..=b'9') = self.next() {
v = v * I::from(10) + I::from((c - b'0') as i8);
}
return Some(v);
}
Some(b'-') => match self.next() {
Some(c @ b'0'..=b'9') => {
let mut v = I::from(-((c - b'0') as i8));
while let Some(c @ b'0'..=b'9') = self.next() {
v = v * I::from(10) - I::from((c - b'0') as i8);
}
return Some(v);
}
_ => return None,
},
Some(_) => continue,
_ => return None,
}
}
}
}
impl<R: std::io::BufRead> Drop for ProconIBufIter<R> {
/// Saving the pointer on interruption
fn drop(&mut self) {
self.inner
.consume(unsafe { ptr_offset_u8(self.ptr, self.raw) });
}
}
/// Insufficient write buffer size causes undefined operation.
pub struct ProconWriteBuffer(*mut u8, Vec<u8>, Dec4le);
impl ProconWriteBuffer {
pub fn with_capacity(capacity: usize) -> Self {
let mut b = Vec::<u8>::with_capacity(capacity);
let ptr = b.as_mut_ptr();
Self(ptr, b, Dec4le::new())
}
pub fn get_mut_ptr(&self) -> *mut u8 {
self.0
}
pub fn set_mut_ptr(&mut self, p: *mut u8) {
self.0 = p;
}
fn decision(&mut self) {
let bptr = self.1.as_mut_ptr();
unsafe { self.1.set_len((self.0 as usize) - (bptr as usize)) };
}
pub fn clear(&mut self) {
self.1.clear();
self.0 = self.1.as_mut_ptr();
}
pub fn get_slice(&mut self) -> &[u8] {
self.decision();
self.1.as_slice()
}
pub fn reserve(&mut self, additional: usize) {
self.decision();
self.1.reserve(additional);
self.0 = self.1.as_mut_ptr();
}
pub fn reserve_exact(&mut self, additional: usize) {
self.decision();
self.1.reserve_exact(additional);
self.0 = self.1.as_mut_ptr();
}
pub fn uint<U>(&mut self, d: U)
where
U: UPrimInt + std::convert::Into<u128>,
{
match U::BITS {
0..=64 => unsafe {
self.2
.rawbytes_ow_u64(&mut self.0, Into::<u128>::into(d) as u64)
},
_ => unsafe { self.2.rawbytes_ow_u128(&mut self.0, Into::<u128>::into(d)) },
}
}
pub fn uint_sp<U>(&mut self, s: &[U])
where
U: UPrimInt + std::convert::Into<u128>,
{
if s.is_empty() {
return;
}
let mut p = self.0;
for &d in s.iter() {
match U::BITS {
0..=64 => unsafe {
self.2
.rawbytes_spow_u64(&mut p, Into::<u128>::into(d) as u64)
},
_ => unsafe { self.2.rawbytes_spow_u128(&mut p, Into::<u128>::into(d)) },
}
}
self.0 = unsafe { p.sub(1) };
}
pub fn uint_splf<U>(&mut self, s: &[U])
where
U: UPrimInt + std::convert::Into<u128>,
{
if s.is_empty() {
proconwritebuf_lf(&mut self.0);
return;
}
let mut p = self.0;
for &d in s.iter() {
match U::BITS {
0..=64 => unsafe {
self.2
.rawbytes_spow_u64(&mut p, Into::<u128>::into(d) as u64)
},
_ => unsafe { self.2.rawbytes_spow_u128(&mut p, Into::<u128>::into(d)) },
}
}
unsafe { *p.sub(1) = b'\n' };
self.0 = p;
}
pub fn usize(&mut self, d: usize) {
unsafe { self.2.rawbytes_ow_u64(&mut self.0, d as u64) };
}
pub fn usize_sp(&mut self, s: &[usize]) {
if s.is_empty() {
return;
}
let mut p = self.0;
for &d in s.iter() {
unsafe { self.2.rawbytes_spow_u64(&mut p, d as u64) };
}
self.0 = unsafe { p.sub(1) };
}
pub fn usize_splf(&mut self, s: &[usize]) {
if s.is_empty() {
proconwritebuf_lf(&mut self.0);
return;
}
let mut p = self.0;
for &d in s.iter() {
unsafe { self.2.rawbytes_spow_u64(&mut p, d as u64) };
}
unsafe { *p.sub(1) = b'\n' };
self.0 = p;
}
pub fn iint<I>(&mut self, d: I)
where
I: IPrimInt + std::convert::Into<i128>,
{
match I::BITS {
0..=64 => unsafe {
self.2
.rawbytes_ow_i64(&mut self.0, Into::<i128>::into(d) as i64)
},
_ => unsafe { self.2.rawbytes_ow_i128(&mut self.0, Into::<i128>::into(d)) },
}
}
pub fn iint_sp<I>(&mut self, s: &[I])
where
I: IPrimInt + std::convert::Into<i128>,
{
if s.is_empty() {
return;
}
let mut p = self.0;
for &d in s.iter() {
match I::BITS {
0..=64 => unsafe {
self.2
.rawbytes_spow_i64(&mut p, Into::<i128>::into(d) as i64)
},
_ => unsafe { self.2.rawbytes_spow_i128(&mut p, Into::<i128>::into(d)) },
}
}
self.0 = unsafe { p.sub(1) };
}
pub fn iint_splf<I>(&mut self, s: &[I])
where
I: IPrimInt + std::convert::Into<i128> + std::convert::TryInto<u8>,
{
if s.is_empty() {
proconwritebuf_lf(&mut self.0);
return;
}
let mut p = self.0;
for &d in s.iter() {
match I::BITS {
0..=64 => unsafe {
self.2
.rawbytes_spow_i64(&mut p, Into::<i128>::into(d) as i64)
},
_ => unsafe { self.2.rawbytes_spow_i128(&mut p, Into::<i128>::into(d)) },
}
}
unsafe { *p.sub(1) = b'\n' };
self.0 = p;
}
pub fn sp(&mut self) {
proconwritebuf_sp(&mut self.0);
}
pub fn lf(&mut self) {
proconwritebuf_lf(&mut self.0);
}
pub fn bytes(&mut self, s: &[u8]) {
proconwritebuf_bytes(&mut self.0, s);
}
pub fn str(&mut self, s: &str) {
proconwritebuf_str(&mut self.0, s);
}
pub fn string(&mut self, s: &String) {
proconwritebuf_string(&mut self.0, s);
}
pub fn write_all<W>(&mut self, out: &mut W)
where
W: std::io::Write,
{
self.decision();
let _ = out.write_all(self.1.as_slice());
self.1.clear();
self.0 = self.1.as_mut_ptr();
}
}
pub fn proconwritebuf_sp(p: &mut *mut u8) {
*p = unsafe {
**p = b' ';
(*p).add(1)
}
}
pub fn proconwritebuf_lf(p: &mut *mut u8) {
*p = unsafe {
**p = b'\n';
(*p).add(1)
}
}
pub fn proconwritebuf_bytes(p: &mut *mut u8, bytes: &[u8]) {
*p = unsafe {
let len = bytes.len();
std::ptr::copy_nonoverlapping(bytes.as_ptr(), *p, len);
(*p).add(len)
};
}
pub fn proconwritebuf_str(p: &mut *mut u8, s: &str) {
*p = unsafe {
let len = s.len();
std::ptr::copy_nonoverlapping(s.as_ptr(), *p, len);
(*p).add(len)
};
}
pub fn proconwritebuf_string(p: &mut *mut u8, s: &String) {
*p = unsafe {
let len = s.len();
std::ptr::copy_nonoverlapping(s.as_ptr(), *p, len);
(*p).add(len)
};
}
pub struct Dec4le((), (), [u32; 100], [u32; 1000], [u32; 10000]);
//pub const DEC4LE: Dec4le = Dec4le::new();
impl Dec4le {
pub fn new() -> Self {
// const fn while: Rust 1.46.0 or later
let (mut d2, mut i) = ([0u32; 100], 0);
while i < 100 {
d2[i as usize] = ((i % 10) << 8) | (i / 10) | 0x0020_3030;
i += 1;
}
let (mut d3, mut i) = ([0u32; 1000], 0);
while i < 1000 {
let (dh, dl) = (i / 100, i % 100);
d3[i as usize] = ((dl % 10) << 16) | ((dl / 10) << 8) | dh | 0x2030_3030;
i += 1;
}
let (mut d4, mut i) = ([0u32; 10000], 0);
while i < 1_0000 {
let (dh, dl) = (i / 100, i % 100);
d4[i as usize] = 0x30303030
| (dh / 10)
| ((dh % 10) << 8)
| ((dl / 10) << 16)
| ((dl % 10) << 24);
i += 1;
}
Self((), (), d2, d3, d4)
}
#[inline(always)]
unsafe fn rawbytes_d1(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 10);
**v = b'0' | x as u8;
*v = v.add(1);
}
#[inline(always)]
unsafe fn rawbytes_d2(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 100);
let s = (((x * 103 >> 10) * 246 + x) as u16 | 0x3030).to_be_bytes();
v.copy_from_nonoverlapping(s.as_ptr(), 2);
*v = v.add(2);
}
#[inline(always)]
unsafe fn rawbytes_d3(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1000);
v.copy_from_nonoverlapping(self.3[x as usize].to_le_bytes().as_ptr(), 3);
*v = v.add(3);
}
#[inline(always)]
unsafe fn rawbytes_d3ow(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1000);
v.copy_from_nonoverlapping(self.3[x as usize].to_le_bytes().as_ptr(), 4);
*v = v.add(3);
}
#[inline(always)]
unsafe fn rawbytes_d4(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1_0000);
v.copy_from_nonoverlapping(self.4[x as usize].to_le_bytes().as_ptr(), 4);
*v = v.add(4);
}
#[inline(always)]
unsafe fn rawbytes_d5(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 10_0000);
let (y0, y1) = (x / 10, x % 10);
v.copy_from_nonoverlapping(
(((y1 as u64) << 32) | (self.4[y0 as usize] as u64) | 0x0030_0000_0000)
.to_le_bytes()
.as_ptr(),
5,
);
*v = v.add(5);
}
#[inline(always)]
unsafe fn rawbytes_d5ow(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 10_0000);
let (y0, y1) = (x / 10, x % 10);
v.copy_from_nonoverlapping(
(((y1 as u64) << 32) | (self.4[y0 as usize] as u64) | 0x0030_0000_0000)
.to_le_bytes()
.as_ptr(),
8,
);
*v = v.add(5);
}
#[inline(always)]
unsafe fn rawbytes_d6(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 100_0000);
let (y0, y1) = (x / 100, x % 100);
v.copy_from_nonoverlapping(
((((self.2[y1 as usize] as u16) as u64) << 32) | (self.4[y0 as usize] as u64))
.to_le_bytes()
.as_ptr(),
6,
);
*v = v.add(6);
}
#[inline(always)]
unsafe fn rawbytes_d6ow(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 100_0000);
let (y0, y1) = (x / 100, x % 100);
v.copy_from_nonoverlapping(
((((self.2[y1 as usize] as u16) as u64) << 32) | (self.4[y0 as usize] as u64))
.to_le_bytes()
.as_ptr(),
8,
);
*v = v.add(6);
}
#[inline(always)]
unsafe fn rawbytes_d7(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1000_0000);
let (y0, y1) = (x / 1000, x % 1000);
v.copy_from_nonoverlapping(
(((self.3[y1 as usize] as u64) << 32) | (self.4[y0 as usize] as u64))
.to_le_bytes()
.as_ptr(),
7,
);
*v = v.add(7);
}
#[inline(always)]
unsafe fn rawbytes_d7ow(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1000_0000);
let (y0, y1) = (x / 1000, x % 1000);
v.copy_from_nonoverlapping(
(((self.3[y1 as usize] as u64) << 32) | (self.4[y0 as usize] as u64))
.to_le_bytes()
.as_ptr(),
8,
);
*v = v.add(7);
}
#[inline(always)]
unsafe fn rawbytes_d8(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1_0000_0000);
let (y0, y1) = (x / 1_0000, x % 1_0000);
v.copy_from_nonoverlapping(
(((self.4[y1 as usize] as u64) << 32) | (self.4[y0 as usize] as u64))
.to_le_bytes()
.as_ptr(),
8,
);
*v = v.add(8);
}
#[inline(always)]
unsafe fn rawbytes_d16(&self, v: &mut *mut u8, x: u64) {
invariant!(x < 1_0000_0000_0000_0000);
let (y0, y1) = ((x / 1_0000_0000) as u32, (x % 1_0000_0000) as u32);
let (z0, z1, z2, z3) = (y0 / 1_0000, y0 % 1_0000, y1 / 1_0000, y1 % 1_0000);
invariant!(z0 < 1_0000 && z1 < 1_0000 && z2 < 1_0000 && z3 < 1_0000);
v.copy_from_nonoverlapping(
(((self.4[z3 as usize] as u128) << 96)
| ((self.4[z2 as usize] as u128) << 64)
| ((self.4[z1 as usize] as u128) << 32)
| (self.4[z0 as usize] as u128))
.to_le_bytes()
.as_ptr(),
16,
);
*v = v.add(16);
}
#[inline(always)]
unsafe fn rawbytes_d1sp(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 10);
v.copy_from_nonoverlapping(((x as u16) | 0x2030).to_le_bytes().as_ptr(), 2);
*v = v.add(2);
}
#[inline(always)]
unsafe fn rawbytes_d2sp(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 100);
v.copy_from_nonoverlapping(self.2[x as usize].to_le_bytes().as_ptr(), 2);
*v.add(2) = b' ';
*v = v.add(3);
}
#[inline(always)]
unsafe fn rawbytes_d2spow(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 100);
v.copy_from_nonoverlapping(self.2[x as usize].to_le_bytes().as_ptr(), 4);
*v = v.add(3);
}
#[inline(always)]
unsafe fn rawbytes_d3sp(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1000);
v.copy_from_nonoverlapping(self.3[x as usize].to_le_bytes().as_ptr(), 4);
*v = v.add(4);
}
#[inline(always)]
unsafe fn rawbytes_d4sp(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1_0000);
v.copy_from_nonoverlapping(self.4[x as usize].to_le_bytes().as_ptr(), 4);
*v.add(4) = b' ';
*v = v.add(5);
}
#[inline(always)]
unsafe fn rawbytes_d5sp(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 10_0000);
let (y0, y1) = (x / 10, x % 10);
v.copy_from_nonoverlapping(
(((y1 as u64) << 32) | (self.4[y0 as usize] as u64) | 0x2030_0000_0000)
.to_le_bytes()
.as_ptr(),
6,
);
*v = v.add(6);
}
#[inline(always)]
unsafe fn rawbytes_d5spow(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 10_0000);
let (y0, y1) = (x / 10, x % 10);
v.copy_from_nonoverlapping(
(((y1 as u64) << 32) | (self.4[y0 as usize] as u64) | 0x2030_0000_0000)
.to_le_bytes()
.as_ptr(),
8,
);
*v = v.add(6);
}
#[inline(always)]
unsafe fn rawbytes_d6sp(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 100_0000);
let (y0, y1) = (x / 1000, x % 1000);
v.copy_from_nonoverlapping(
(((self.3[y1 as usize] as u64) << 24) | (self.3[y0 as usize] as u64))
.to_le_bytes()
.as_ptr(),
7,
);
*v = v.add(7);
}
#[inline(always)]
unsafe fn rawbytes_d6spow(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 100_0000);
let (y0, y1) = (x / 1000, x % 1000);
v.copy_from_nonoverlapping(
(((self.3[y1 as usize] as u64) << 24) | (self.3[y0 as usize] as u64))
.to_le_bytes()
.as_ptr(),
8,
);
*v = v.add(7);
}
#[inline(always)]
unsafe fn rawbytes_d7sp(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1000_0000);
let (y0, y1) = (x / 1000, x % 1000);
v.copy_from_nonoverlapping(
(((self.3[y1 as usize] as u64) << 32) | (self.4[y0 as usize] as u64))
.to_le_bytes()
.as_ptr(),
8,
);
*v = v.add(8);
}
#[inline(always)]
unsafe fn rawbytes_d8sp(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1_0000_0000);
let (y0, y1) = (x / 1_0000, x % 1_0000);
v.copy_from_nonoverlapping(
(((self.4[y1 as usize] as u64) << 32) | (self.4[y0 as usize] as u64))
.to_le_bytes()
.as_ptr(),
8,
);
*v.add(8) = b' ';
*v = v.add(9);
}
#[inline(always)]
unsafe fn rawbytes_d16sp(&self, v: &mut *mut u8, x: u64) {
invariant!(x < 1_0000_0000_0000_0000);
let (y0, y1) = ((x / 1_0000_0000) as u32, (x % 1_0000_0000) as u32);
let (z0, z1, z2, z3) = (y0 / 1_0000, y0 % 1_0000, y1 / 1_0000, y1 % 1_0000);
invariant!(z0 < 1_0000 && z1 < 1_0000 && z2 < 1_0000 && z3 < 1_0000);
v.copy_from_nonoverlapping(
(((self.4[z3 as usize] as u128) << 96)
| ((self.4[z2 as usize] as u128) << 64)
| ((self.4[z1 as usize] as u128) << 32)
| (self.4[z0 as usize] as u128))
.to_le_bytes()
.as_ptr(),
16,
);
*v.add(16) = b' ';
*v = v.add(17);
}
#[inline(always)]
pub unsafe fn rawbytes_d8less(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1_0000_0000);
match x {
0..=9 => self.rawbytes_d1(v, x),
10..=99 => self.rawbytes_d2(v, x),
100..=999 => self.rawbytes_d3(v, x),
1000..=9999 => self.rawbytes_d4(v, x),
1_0000..=9_9999 => self.rawbytes_d5(v, x),
10_0000..=99_9999 => self.rawbytes_d6(v, x),
100_0000..=999_9999 => self.rawbytes_d7(v, x),
1000_0000..=9999_9999 => self.rawbytes_d8(v, x),
_ => core::hint::unreachable_unchecked(),
}
}
#[inline(always)]
pub unsafe fn rawbytes_d8less_ow(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1_0000_0000);
match x {
0..=9 => self.rawbytes_d1(v, x),
10..=99 => self.rawbytes_d2(v, x),
100..=999 => self.rawbytes_d3ow(v, x),
1000..=9999 => self.rawbytes_d4(v, x),
1_0000..=9_9999 => self.rawbytes_d5ow(v, x),
10_0000..=99_9999 => self.rawbytes_d6ow(v, x),
100_0000..=999_9999 => self.rawbytes_d7ow(v, x),
1000_0000..=9999_9999 => self.rawbytes_d8(v, x),
_ => core::hint::unreachable_unchecked(),
}
}
#[inline(always)]
pub unsafe fn rawbytes_d8less_sp(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1_0000_0000);
match x {
0..=9 => self.rawbytes_d1sp(v, x),
10..=99 => self.rawbytes_d2sp(v, x),
100..=999 => self.rawbytes_d3sp(v, x),
1000..=9999 => self.rawbytes_d4sp(v, x),
1_0000..=9_9999 => self.rawbytes_d5sp(v, x),
10_0000..=99_9999 => self.rawbytes_d6sp(v, x),
100_0000..=999_9999 => self.rawbytes_d7sp(v, x),
1000_0000..=9999_9999 => self.rawbytes_d8sp(v, x),
_ => core::hint::unreachable_unchecked(),
}
}
#[inline(always)]
pub unsafe fn rawbytes_d8less_spow(&self, v: &mut *mut u8, x: u32) {
invariant!(x < 1_0000_0000);
match x {
0..=9 => self.rawbytes_d1sp(v, x),
10..=99 => self.rawbytes_d2spow(v, x),
100..=999 => self.rawbytes_d3sp(v, x),
1000..=9999 => self.rawbytes_d4sp(v, x),
1_0000..=9_9999 => self.rawbytes_d5spow(v, x),
10_0000..=99_9999 => self.rawbytes_d6spow(v, x),
100_0000..=999_9999 => self.rawbytes_d7sp(v, x),
1000_0000..=9999_9999 => self.rawbytes_d8sp(v, x),
_ => core::hint::unreachable_unchecked(),
}
}
#[inline(always)]
pub unsafe fn rawbytes_u64(&self, v: &mut *mut u8, x: u64) {
match x {
0..=9999_9999 => self.rawbytes_d8less(v, x as u32),
1_0000_0000..=9999_9999_9999_9999 => {
let (z0, z1) = ((x / 1_0000_0000) as u32, (x % 1_0000_0000) as u32);
self.rawbytes_d8less_ow(v, z0);
self.rawbytes_d8(v, z1);
}
1_0000_0000_0000_0000..=1844_6744_0737_0955_1615 => {
let (y0, y1) = (
(x / 1_0000_0000_0000_0000) as u32,
x % 1_0000_0000_0000_0000,
);
invariant!(y0 < 1845);
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16(v, y1);
}
}
}
#[inline(always)]
pub unsafe fn rawbytes_ow_u64(&self, v: &mut *mut u8, x: u64) {
match x {
0..=9999_9999 => self.rawbytes_d8less_ow(v, x as u32),
1_0000_0000..=9999_9999_9999_9999 => {
let (z0, z1) = ((x / 1_0000_0000) as u32, (x % 1_0000_0000) as u32);
self.rawbytes_d8less_ow(v, z0);
self.rawbytes_d8(v, z1);
}
1_0000_0000_0000_0000..=1844_6744_0737_0955_1615 => {
let (y0, y1) = (
(x / 1_0000_0000_0000_0000) as u32,
x % 1_0000_0000_0000_0000,
);
invariant!(y0 < 1845);
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16(v, y1);
}
}
}
#[inline(always)]
pub unsafe fn rawbytes_sp_u64(&self, v: &mut *mut u8, x: u64) {
match x {
0..=9999_9999 => self.rawbytes_d8less_sp(v, x as u32),
1_0000_0000..=9999_9999_9999_9999 => {
let (z0, z1) = ((x / 1_0000_0000) as u32, (x % 1_0000_0000) as u32);
self.rawbytes_d8less_ow(v, z0);
self.rawbytes_d8sp(v, z1);
}
1_0000_0000_0000_0000..=1844_6744_0737_0955_1615 => {
let (y0, y1) = (
(x / 1_0000_0000_0000_0000) as u32,
x % 1_0000_0000_0000_0000,
);
invariant!(y0 < 1845);
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16sp(v, y1);
}
}
}
#[inline(always)]
pub unsafe fn rawbytes_spow_u64(&self, v: &mut *mut u8, x: u64) {
match x {
0..=9999_9999 => self.rawbytes_d8less_spow(v, x as u32),
1_0000_0000..=9999_9999_9999_9999 => {
let (z0, z1) = ((x / 1_0000_0000) as u32, (x % 1_0000_0000) as u32);
self.rawbytes_d8less_ow(v, z0);
self.rawbytes_d8sp(v, z1);
}
1_0000_0000_0000_0000..=1844_6744_0737_0955_1615 => {
let (y0, y1) = (
(x / 1_0000_0000_0000_0000) as u32,
x % 1_0000_0000_0000_0000,
);
invariant!(y0 < 1845);
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16sp(v, y1);
}
}
}
#[inline(always)]
pub unsafe fn rawbytes_u128(&self, v: &mut *mut u8, x: u128) {
match x {
0..=9999_9999 => self.rawbytes_d8less(v, x as u32),
1_0000_0000..=9999_9999_9999_9999 => {
let (z0, z1) = ((x / 1_0000_0000) as u32, (x % 1_0000_0000) as u32);
self.rawbytes_d8less_ow(v, z0);
self.rawbytes_d8(v, z1);
}
1_0000_0000_0000_0000..=1844_6744_0737_0955_1615 => {
let (y0, y1) = (
(x / 1_0000_0000_0000_0000) as u32,
(x % 1_0000_0000_0000_0000) as u64,
);
invariant!(y0 < 1845);
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16(v, y1);
}
1844_6744_0737_0955_1616..=9999_9999_9999_9999_9999_9999 => {
let y0 = (x / 1_0000_0000_0000_0000) as u32;
let y1 = (x - (y0 as u128) * 1_0000_0000_0000_0000) as u64;
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16(v, y1);
}
1_0000_0000_0000_0000_0000_0000..=9999_9999_9999_9999_9999_9999_9999_9999 => {
let y0 = (x / 1_0000_0000_0000_0000) as u64;
let y1 = (x - (y0 as u128) * 1_0000_0000_0000_0000) as u64;
let (z0, z1) = ((y0 / 1_0000_0000) as u32, (y0 % 1_0000_0000) as u32);
self.rawbytes_d8less_ow(v, z0);
self.rawbytes_d8(v, z1);
self.rawbytes_d16(v, y1);
}
1_0000_0000_0000_0000_0000_0000_0000_0000
..=340_2823_6692_0938_4634_6337_4607_4317_6821_1455 => {
let y0 = (x / 1_0000_0000_0000_0000_0000_0000_0000_0000) as u32;
let y1 = x - (y0 as u128) * 1_0000_0000_0000_0000_0000_0000_0000_0000;
let z0 = (y1 / 1_0000_0000_0000_0000) as u64;
let z1 = (y1 - (z0 as u128) * 1_0000_0000_0000_0000) as u64;
invariant!(y0 < 340_2824);
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16(v, z0);
self.rawbytes_d16(v, z1);
}
}
}
#[inline(always)]
pub unsafe fn rawbytes_ow_u128(&self, v: &mut *mut u8, x: u128) {
match x {
0..=9999_9999 => self.rawbytes_d8less_ow(v, x as u32),
1_0000_0000..=9999_9999_9999_9999 => {
let (z0, z1) = ((x / 1_0000_0000) as u32, (x % 1_0000_0000) as u32);
self.rawbytes_d8less_ow(v, z0);
self.rawbytes_d8(v, z1);
}
1_0000_0000_0000_0000..=1844_6744_0737_0955_1615 => {
let (y0, y1) = (
(x / 1_0000_0000_0000_0000) as u32,
(x % 1_0000_0000_0000_0000) as u64,
);
invariant!(y0 < 1845);
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16(v, y1);
}
1844_6744_0737_0955_1616..=9999_9999_9999_9999_9999_9999 => {
let y0 = (x / 1_0000_0000_0000_0000) as u32;
let y1 = (x - (y0 as u128) * 1_0000_0000_0000_0000) as u64;
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16(v, y1);
}
1_0000_0000_0000_0000_0000_0000..=9999_9999_9999_9999_9999_9999_9999_9999 => {
let y0 = (x / 1_0000_0000_0000_0000) as u64;
let y1 = (x - (y0 as u128) * 1_0000_0000_0000_0000) as u64;
let (z0, z1) = ((y0 / 1_0000_0000) as u32, (y0 % 1_0000_0000) as u32);
self.rawbytes_d8less_ow(v, z0);
self.rawbytes_d8(v, z1);
self.rawbytes_d16(v, y1);
}
1_0000_0000_0000_0000_0000_0000_0000_0000
..=340_2823_6692_0938_4634_6337_4607_4317_6821_1455 => {
let y0 = (x / 1_0000_0000_0000_0000_0000_0000_0000_0000) as u32;
let y1 = x - (y0 as u128) * 1_0000_0000_0000_0000_0000_0000_0000_0000;
let z0 = (y1 / 1_0000_0000_0000_0000) as u64;
let z1 = (y1 - (z0 as u128) * 1_0000_0000_0000_0000) as u64;
invariant!(y0 < 340_2824);
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16(v, z0);
self.rawbytes_d16(v, z1);
}
}
}
#[inline(always)]
pub unsafe fn rawbytes_sp_u128(&self, v: &mut *mut u8, x: u128) {
match x {
0..=9999_9999 => self.rawbytes_d8less_sp(v, x as u32),
1_0000_0000..=9999_9999_9999_9999 => {
let (z0, z1) = ((x / 1_0000_0000) as u32, (x % 1_0000_0000) as u32);
self.rawbytes_d8less_ow(v, z0);
self.rawbytes_d8sp(v, z1);
}
1_0000_0000_0000_0000..=1844_6744_0737_0955_1615 => {
let (y0, y1) = (
(x / 1_0000_0000_0000_0000) as u32,
(x % 1_0000_0000_0000_0000) as u64,
);
invariant!(y0 < 1845);
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16sp(v, y1);
}
1844_6744_0737_0955_1616..=9999_9999_9999_9999_9999_9999 => {
let y0 = (x / 1_0000_0000_0000_0000) as u32;
let y1 = (x - (y0 as u128) * 1_0000_0000_0000_0000) as u64;
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16sp(v, y1);
}
1_0000_0000_0000_0000_0000_0000..=9999_9999_9999_9999_9999_9999_9999_9999 => {
let y0 = (x / 1_0000_0000_0000_0000) as u64;
let y1 = (x - (y0 as u128) * 1_0000_0000_0000_0000) as u64;
let (z0, z1) = ((y0 / 1_0000_0000) as u32, (y0 % 1_0000_0000) as u32);
self.rawbytes_d8less_ow(v, z0);
self.rawbytes_d8(v, z1);
self.rawbytes_d16sp(v, y1);
}
1_0000_0000_0000_0000_0000_0000_0000_0000
..=340_2823_6692_0938_4634_6337_4607_4317_6821_1455 => {
let y0 = (x / 1_0000_0000_0000_0000_0000_0000_0000_0000) as u32;
let y1 = x - (y0 as u128) * 1_0000_0000_0000_0000_0000_0000_0000_0000;
let z0 = (y1 / 1_0000_0000_0000_0000) as u64;
let z1 = (y1 - (z0 as u128) * 1_0000_0000_0000_0000) as u64;
invariant!(y0 < 340_2824);
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16(v, z0);
self.rawbytes_d16sp(v, z1);
}
}
}
#[inline(always)]
pub unsafe fn rawbytes_spow_u128(&self, v: &mut *mut u8, x: u128) {
match x {
0..=9999_9999 => self.rawbytes_d8less_spow(v, x as u32),
1_0000_0000..=9999_9999_9999_9999 => {
let (z0, z1) = ((x / 1_0000_0000) as u32, (x % 1_0000_0000) as u32);
self.rawbytes_d8less_ow(v, z0);
self.rawbytes_d8sp(v, z1);
}
1_0000_0000_0000_0000..=1844_6744_0737_0955_1615 => {
let (y0, y1) = (
(x / 1_0000_0000_0000_0000) as u32,
(x % 1_0000_0000_0000_0000) as u64,
);
invariant!(y0 < 1845);
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16sp(v, y1);
}
1844_6744_0737_0955_1616..=9999_9999_9999_9999_9999_9999 => {
let y0 = (x / 1_0000_0000_0000_0000) as u32;
let y1 = (x - (y0 as u128) * 1_0000_0000_0000_0000) as u64;
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16sp(v, y1);
}
1_0000_0000_0000_0000_0000_0000..=9999_9999_9999_9999_9999_9999_9999_9999 => {
let y0 = (x / 1_0000_0000_0000_0000) as u64;
let y1 = (x - (y0 as u128) * 1_0000_0000_0000_0000) as u64;
let (z0, z1) = ((y0 / 1_0000_0000) as u32, (y0 % 1_0000_0000) as u32);
self.rawbytes_d8less_ow(v, z0);
self.rawbytes_d8(v, z1);
self.rawbytes_d16sp(v, y1);
}
1_0000_0000_0000_0000_0000_0000_0000_0000
..=340_2823_6692_0938_4634_6337_4607_4317_6821_1455 => {
let y0 = (x / 1_0000_0000_0000_0000_0000_0000_0000_0000) as u32;
let y1 = x - (y0 as u128) * 1_0000_0000_0000_0000_0000_0000_0000_0000;
let z0 = (y1 / 1_0000_0000_0000_0000) as u64;
let z1 = (y1 - (z0 as u128) * 1_0000_0000_0000_0000) as u64;
invariant!(y0 < 340_2824);
self.rawbytes_d8less_ow(v, y0);
self.rawbytes_d16(v, z0);
self.rawbytes_d16sp(v, z1);
}
}
}
#[inline(always)]
pub unsafe fn rawbytes_ow_i64(&self, v: &mut *mut u8, x: i64) {
let x = if x < 0 {
**v = b'-';
*v = v.add(1);
x.wrapping_neg() as u64
} else {
x as u64
};
self.rawbytes_ow_u64(v, x);
}
#[inline(always)]
pub unsafe fn rawbytes_sp_i64(&self, v: &mut *mut u8, x: i64) {
let x = if x < 0 {
**v = b'-';
*v = v.add(1);
x.wrapping_neg() as u64
} else {
x as u64
};
self.rawbytes_sp_u64(v, x);
}
#[inline(always)]
pub unsafe fn rawbytes_spow_i64(&self, v: &mut *mut u8, x: i64) {
let x = if x < 0 {
**v = b'-';
*v = v.add(1);
x.wrapping_neg() as u64
} else {
x as u64
};
self.rawbytes_spow_u64(v, x);
}
#[inline(always)]
pub unsafe fn rawbytes_ow_i128(&self, v: &mut *mut u8, x: i128) {
let x = if x < 0 {
**v = b'-';
*v = v.add(1);
x.wrapping_neg() as u128
} else {
x as u128
};
self.rawbytes_ow_u128(v, x);
}
#[inline(always)]
pub unsafe fn rawbytes_sp_i128(&self, v: &mut *mut u8, x: i128) {
let x = if x < 0 {
**v = b'-';
*v = v.add(1);
x.wrapping_neg() as u128
} else {
x as u128
};
self.rawbytes_sp_u128(v, x);
}
#[inline(always)]
pub unsafe fn rawbytes_spow_i128(&self, v: &mut *mut u8, x: i128) {
let x = if x < 0 {
**v = b'-';
*v = v.add(1);
x.wrapping_neg() as u128
} else {
x as u128
};
self.rawbytes_spow_u128(v, x);
}
}
}
#[cfg(not(target_os = "linux"))]
pub fn print(s: &[u8]) {
std::io::Write::write_all(&mut std::io::stdout(), s).unwrap();
}
#[cfg(not(target_os = "linux"))]
#[allow(unused)]
pub fn print_err(s: &[u8]) {
std::io::Write::write_all(&mut std::io::stderr(), s).unwrap();
}
#[cfg(not(target_os = "linux"))]
#[no_mangle]
pub fn ilaunch() {
let stdin = std::io::stdin();
solve(&mut fastproconio::ProconIBufIter::new(stdin.lock()));
}
#[cfg(target_os = "linux")]
pub fn print(s: &[u8]) {
unsafe { write(1, s.as_ptr(), s.len()) };
}
#[cfg(target_os = "linux")]
pub fn print_err(s: &[u8]) {
unsafe { write(2, s.as_ptr(), s.len()) };
}
#[cfg(target_os = "linux")]
#[link(name = "c")]
#[rustfmt::skip]
extern "C" {
pub fn mmap(addr: *mut u8, length: usize, prot: i32, flags: i32, fd: i32, off: isize) -> *mut u8;
pub fn munmap(addr: *mut u8, length: usize) -> i32;
pub fn read(fd: i32, buf: *mut u8, len: usize) -> usize;
pub fn write(fd: i32, s: *const u8, len: usize);
}
#[cfg(target_os = "linux")]
pub fn ilaunch() {
unsafe {
use std::os::unix::io::FromRawFd;
match std::fs::File::from_raw_fd(0).metadata() {
Ok(metadata) if metadata.is_file() => {
let filelen = metadata.len();
let input = mmap(std::ptr::null_mut(), filelen as usize, 1, 2, 0, 0);
solve(&mut fastproconio::BytesIter(std::slice::from_raw_parts(
input,
filelen as usize,
)));
}
_ => {
let stdin = std::io::stdin();
solve(&mut fastproconio::ProconIBufIter::new(stdin.lock()));
}
}
}
}
fn main() {
const USE_THREAD: bool = false;
if USE_THREAD {
// In order to avoid potential stack overflow, spawn a new thread.
let stack_size = 134_217_728; // 128 MB
let thd = std::thread::Builder::new().stack_size(stack_size);
thd.spawn(|| ilaunch()).unwrap().join().unwrap();
} else {
ilaunch()
}
}
/// ニュートン・ラフソン法による整数平方根 $`\left\lfloor\sqrt{x}\right\rfloor`$
///
/// - $`s_{n+1}=\lfloor(s_n+\lfloor a/s_n\rfloor)/2\rfloor`$ とする。 $`s_n\in\mathbb{N},\ a\in\mathbb{N},\ s_n\ge 1,\ a\ge 1`$ であるとする。
/// - (補題) $`s_n`$ は自然数であるから、
/// ```math
/// s_{n+1}=\left\lfloor\left(s_n+\left\lfloor\frac{a}{s_n}\right\rfloor\right)/2\right\rfloor=\left\lfloor\left\lfloor s_n+\frac{a}{s_n}\right\rfloor/2\right\rfloor=\left\lfloor\left(s_n+\frac{a}{s_n}\right)/2\right\rfloor=\left\lfloor\frac{s_n^2+a}{2s_n}\right\rfloor
/// ```
/// - (1) $`s_n\gt\left\lfloor\sqrt{a}\right\rfloor`$ のとき、 $`\left\lfloor\sqrt{a}\right\rfloor\le s_{n+1}\lt s_n`$ である。(この条件の間は単調減少する保証)
/// - $`s_n\gt\left\lfloor\sqrt{a}\right\rfloor`$ より $`s_n\gt\sqrt{a}`$ であり、 $`\varepsilon\gt 0`$ を使って $`s_n=(1+\varepsilon)\sqrt{a}`$ とすると、
/// ```math
/// \left\lfloor\sqrt{a}\right\rfloor\le\left\lfloor\frac{2+2\varepsilon+\varepsilon^2}{2(1+\varepsilon)}\sqrt{a}\right\rfloor=\left\lfloor\frac{s_n^2+a}{2s_n}\right\rfloor=s_{n+1}\le\frac{s_n^2+a}{2s_n}\lt\frac{s_n^2+s_n^2}{2s_n}=s_n
/// ```
/// - (2) $`s_n=\left\lfloor\sqrt{a}\right\rfloor`$ のとき、 $`\left\lfloor\sqrt{a}\right\rfloor\le s_{n+1}\le\left\lfloor\sqrt{a}\right\rfloor+1`$ である。($`\left\lfloor\sqrt{a}\right\rfloor`$ 到達時の挙動の保証)
/// - $`s_n=\left\lfloor\sqrt{a}\right\rfloor,\quad\sqrt{a}-1\lt s_n\le\sqrt{a}`$ より、 $`s_n^2\le a\lt(s_n+1)^2`$
/// - $`s_n`$ は自然数であるから $`\lfloor s_n\rfloor=s_n`$ および $`\displaystyle{\frac{1}{2s_n}\lt 1}`$ より、
/// ```math
/// \left\lfloor\sqrt{a}\right\rfloor=\left\lfloor\frac{s_n^2+s_n^2}{2s_n}\right\rfloor\le s_{n+1}\le\left\lfloor\frac{s_n^2+(s_n+1)^2}{2s_n}\right\rfloor=\left\lfloor s_n+1+\frac{1}{2s_n}\right\rfloor=\left\lfloor\sqrt{a}\right\rfloor+1
/// ```
pub fn sqrt_floor(x: u64) -> u64 {
if x <= 1 {
return x;
}
let k = 32 - ((x - 1).leading_zeros() >> 1);
let mut s = 1u64 << k; // s = 2^k
let mut t = (s + (x >> k)) >> 1; // t = (s + x/s)/2
// while loop count (= divide count) may be { u64: max 6 times, u32: max 5 times }
// s > floor(sqrt(x)) -> floor(sqrt(x)) <= t < s
// s == floor(sqrt(x)) -> s == floor(sqrt(x)) <= t <= floor(sqrt(x)) + 1
while t < s {
s = t;
t = (s + x / s) >> 1;
}
s
}
/// $`\lceil\sqrt{x}\rceil`$
///
/// See [`sqrt_floor`]
pub fn sqrt_ceil(x: u64) -> u64 {
let s = sqrt_floor(x);
if x > s * s {
s + 1
} else {
s
}
}
/// $`\operatorname{mod} 2^{64}`$での乗法逆元, $`N \times n \mod 2^{64} \equiv 1`$
///
/// - 入力値の整数 $`N`$ は奇数に限る、さもなくば $`N \times n \mod 2^{64} \equiv 1`$を満たす $`n`$ が存在しない
/// - $`\operatorname{mod}`$ が累乗数の場合、ニュートン法によって乗法逆元を計算できる
/// - 特に $`\operatorname{mod}`$ が $`2`$ の累乗数の場合、自身を $`\operatorname{mod}8`$ における乗法逆元としての初期値とする事が出来る $`N \mod 2 \equiv 1 ⇔ N^2 \mod 8 \equiv 1`$
///
/// - 2次収束
/// - 整数 $`N`$ に対して 整数 $`n_j`$ が、 $`Nn_j\mod m\equiv 1`$ を満たす時、
/// $`n_{j+1}`$ を $`n_{j+1}=n_j(2-Nn_j)`$ と定義するなら、
/// $`Nn_{j+1}\mod m^2\equiv 1`$ を満たす。
/// - $`Nn_j=1+km`$ とおくと、 $`Nn_{j+1}=Nn_j(2-Nn_j)=1-(Nn_j-1)^2=1-k^2m^2\equiv 1\quad(\operatorname{mod}\ m^2)`$
/// - 奇数 $`N`$ を $`N=1+2k`$ とおくと、 $`\left(k(1+k)\right)`$ は偶数であるから
/// - $`n_0=N,\quad n_{j+1}=n_j(2-N\,n_j)`$ とした時
/// - $`Nn_0=1+2^3\cdot \left(k(1+k)/2\right)\ \ \to\ \ Nn_0\mod 2^3\equiv 1`$
/// - $`Nn_1=1-2^6\cdot \left(k(1+k)/2\right)^2\ \ \to\ \ Nn_1\mod 2^6\equiv 1`$
/// - $`Nn_2=1-2^{12}\cdot \left(k(1+k)/2\right)^4\ \ \to\ \ Nn_2\mod 2^{12}\equiv 1`$
/// - $`Nn_3=1-2^{24}\cdot \left(k(1+k)/2\right)^8\ \ \to\ \ Nn_3\mod 2^{24}\equiv 1`$
/// - $`Nn_4=1-2^{48}\cdot \left(k(1+k)/2\right)^{16}\ \ \to\ \ Nn_4\mod 2^{48}\equiv 1`$
/// - $`Nn_5=1-2^{96}\cdot \left(k(1+k)/2\right)^{32}\ \ \to\ \ Nn_5\mod 2^{96}\equiv 1`$
/// - 3次収束
/// - 整数 $`N`$ に対して 整数 $`n_j`$ が、 $`Nn_j\mod m\equiv 1`$ を満たす時、
/// $`n_{j+1}`$ を $`n_{j+1}=n_j(Nn_j(Nn_j-3)+3)`$ と定義するなら、
/// $`Nn_{j+1}\mod m^3\equiv 1`$ を満たす。
/// - $`Nn_j=1+km`$ とおくと、 $`Nn_{j+1}=Nn_j(Nn_j(Nn_j-3)+3)=1+(Nn_j-1)^3=1+k^3m^3\equiv 1\quad(\operatorname{mod}\ m^3)`$
/// - 奇数 $`N`$ を $`N=1+2k`$ とおくと、 $`\left(k(1+k)\right)`$ は偶数であるから
/// - $`n_0=N,\quad n_{j+1}=n_j(Nn_j(Nn_j-3)+3)`$ とした時
/// - $`Nn_0=1+2^3\cdot \left(k(1+k)/2\right)\ \ \to\ \ Nn_0\mod 2^3\equiv 1`$
/// - $`Nn_1=1+2^9\cdot \left(k(1+k)/2\right)^3\ \ \to\ \ Nn_1\mod 2^9\equiv 1`$
/// - $`Nn_2=1+2^{27}\cdot \left(k(1+k)/2\right)^9\ \ \to\ \ Nn_2\mod 2^{27}\equiv 1`$
/// - $`Nn_3=1+2^{81}\cdot \left(k(1+k)/2\right)^{27}\ \ \to\ \ Nn_3\mod 2^{81}\equiv 1`$
///
/// See [`u64max_quot`], [`InvDivider::factor`]
pub fn u64mod_inv(n: u64) -> u64 {
debug_assert_eq!(n & 1, 1); // 入力値は奇数に限る
let n32 = n as u32;
let ninv = n32;
let t = n32.wrapping_mul(ninv);
let ninv = ninv.wrapping_mul(t.wrapping_sub(3).wrapping_mul(t).wrapping_add(3));
let t = n32.wrapping_mul(ninv);
let ninv = ninv.wrapping_mul(t.wrapping_sub(3).wrapping_mul(t).wrapping_add(3)) as u64;
let t = n.wrapping_mul(ninv);
let ninv = ninv.wrapping_mul(t.wrapping_sub(3).wrapping_mul(t).wrapping_add(3));
debug_assert_eq!(n.wrapping_mul(ninv), 1); // n * ni mod 2^64 == 1
ninv
}
/// $`\lfloor (2^{64}-1)/n \rfloor`$
///
/// See [`u64mod_inv`], [`InvDivider::factor`]
pub fn u64max_quot(n: u64) -> u64 {
debug_assert_ne!(n, 0);
// u64 / NonZeroU64 (ゼロ除算のエラーチェックを省略) は rust 1.51.0 以降
// unsafe { (!0u64) / std::num::NonZeroU64::new_unchecked(n) }
(!0u64) / n
}
/// 素数計数関数 $`\pi(x)`$ の近似式 (Dusart)
///
/// 確保が必要なメモリ領域の見積もり用に、 $`\pi(x)`$ 以上になる近似式を用いる: 下記の(1)式
///
/// ```math
/// \begin{align}
/// \pi(x) &\lt \frac{x}{\ln(x)}\biggl(1+\frac{1}{\ln(x)}+\frac{2}{\ln^2(x)}+\frac{7.59}{\ln^3(x)}\biggr) \quad (x \gt 1) \\
/// \pi(x) &\gt \frac{x}{\ln(x)}\biggl(1+\frac{1}{\ln(x)}+\frac{2}{\ln^2(x)}\biggr) \quad (x \ge 88789) \\
/// \end{align}
/// ```
///
/// <https://en.wikipedia.org/wiki/Prime-counting_function#Inequalities>
pub fn approx_prime_pi(x: u64) -> u64 {
match x {
0..=1 => 0,
2..=2 => 1,
3..=4 => 2,
5..=6 => 3,
7..=10 => 4,
11..=12 => 5,
13..=16 => 6,
17..=18 => 7,
19..=22 => 8,
23..=28 => 9,
29..=30 => 10,
_ => {
let xf = x as f64;
let iln = 1. / xf.ln();
((1. + (1. + (2. + 7.59 * iln) * iln) * iln) * iln * xf).ceil() as u64
}
}
}
/// 高速なエラトステネスの篩
///
/// * <https://qiita.com/peria/items/a4ff4ddb3336f7b81d50>
/// * <https://github.com/peria/primes/tree/master/eratosthenes>
pub struct Eratosthenes {
x: u64,
flags: Vec<u8>,
}
impl Eratosthenes {
/// CPUキャッシュサイズを考慮した処理単位
///
/// - 最適パラメータの例:
/// - Intel Core i7 7500U (L1dキャッシュ: 32kiB/instance, L2キャッシュ: 256kiB/instance): SEGMENT_SIZE 128kiB が最適
/// ```text
/// Caches (sum of all):
/// L1d: 64 KiB (2 instances)
/// L1i: 64 KiB (2 instances)
/// L2: 512 KiB (2 instances)
/// L3: 4 MiB (1 instance)
/// ```
/// - AMD Ryzen Threadripper 3970X (L1dキャッシュ: 16kiB/instance, L2キャッシュ: 512kiB/instance): SEGMENT_SIZE 512kiB が最適
/// ```text
/// Caches (sum of all):
/// L1d: 1 MiB (32 instances)
/// L1i: 1 MiB (32 instances)
/// L2: 16 MiB (32 instances)
/// L3: 16 MiB (1 instance)
/// ```
//const SEGMENT_SIZE: usize = 65536; // 64kiB
//const SEGMENT_SIZE: usize = 131072; // 128kiB
//const SEGMENT_SIZE: usize = 262144; // 256kiB
const SEGMENT_SIZE: usize = 524288; // 512kiB
//const SEGMENT_SIZE: usize = 1048576; // 1MiB
//const SEGMENT_SIZE: usize = 2097152; // 2MiB
//const SEGMENT_SIZE: usize = 4194304; // 4MiB
//const SEGMENT_SIZE: usize = 8388608; // 8MiB
//const SEGMENT_SIZE: usize = 16777216; // 16MiB
//const SEGMENT_SIZE: usize = 33554432; // 32MiB
//const SEGMENT_SIZE: usize = 67108864; // 64MiB
//const SEGMENT_SIZE: usize = 134217728; // 128MiB
//const SEGMENT_SIZE: usize = 268435456; // 256MiB
/// `[1, 7, 11, 13, 17, 19, 23, 29]`
const MOD_30: [usize; 8] = [1, 7, 11, 13, 17, 19, 23, 29];
/// `[n0-m0 for (n0,m0) in zip(n, m)]`
const C1: [u16; 8] = [6, 4, 2, 4, 2, 4, 6, 2];
/// `[[m0*n1/30-m0*m1/30 for (n1,m1) in zip(n, m)] for m0 in m]`
const C0: [[u16; 8]; 8] = [
[0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 0, 1, 1, 1, 1],
[2, 2, 0, 2, 0, 2, 2, 1],
[3, 1, 1, 2, 1, 1, 3, 1],
[3, 3, 1, 2, 1, 3, 3, 1],
[4, 2, 2, 2, 2, 2, 4, 1],
[5, 3, 1, 4, 1, 3, 5, 1],
[6, 4, 2, 4, 2, 4, 6, 1],
];
/// `[[bitoff(m0*m1%30) for m1 in m] for m0 in m]`
const MASK: [[u8; 8]; 8] = [
[0xfe, 0xfd, 0xfb, 0xf7, 0xef, 0xdf, 0xbf, 0x7f],
[0xfd, 0xdf, 0xef, 0xfe, 0x7f, 0xf7, 0xfb, 0xbf],
[0xfb, 0xef, 0xfe, 0xbf, 0xfd, 0x7f, 0xf7, 0xdf],
[0xf7, 0xfe, 0xbf, 0xdf, 0xfb, 0xfd, 0x7f, 0xef],
[0xef, 0x7f, 0xfd, 0xfb, 0xdf, 0xbf, 0xfe, 0xf7],
[0xdf, 0xf7, 0x7f, 0xfd, 0xbf, 0xfe, 0xef, 0xfb],
[0xbf, 0xfb, 0xf7, 0x7f, 0xfe, 0xef, 0xdf, 0xfd],
[0x7f, 0xbf, 0xdf, 0xef, 0xf7, 0xfb, 0xfd, 0xfe],
];
const BIT_TO_INDEX: [u8; 256] = [
0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0,
1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0,
1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0,
1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0,
2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0,
1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
];
fn bit_to_index(x: u8) -> usize {
Self::BIT_TO_INDEX[x as usize] as usize // == if x == 0 { 0 } else { x.trailing_zeros() as usize }
}
/// エラトステネスの篩の高速化(2) に近い実装
///
/// * <https://qiita.com/peria/items/54499b9ce9d5c1e93e5a>
pub fn generate_v2(x: u64) -> Self {
let flags_size = (x as usize / 30 + if x % 30 != 0 { 1 } else { 0 }).max(1);
// mod 30 == {1, 7, 11, 13, 17, 19, 23, 29} となるビット列 (mod 2,3,5 == 0 をあらかじめリストから除外)
let mut flags = vec![!0u8; flags_size];
// {1} を篩から削除
flags[0] &= 0xfe;
// 末端の調整
flags[flags_size - 1] &= match x % 30 {
0..=0 => 0xff,
1..=6 => 0x01,
7..=10 => 0x03,
11..=12 => 0x07,
13..=16 => 0x0f,
17..=18 => 0x1f,
19..=22 => 0x3f,
23..=28 => 0x7f,
29..=29 => 0xff,
_ => unreachable!(),
};
// ceil(平方根) の計算
let sqrt_x = sqrt_ceil(x);
let sqrt_xi = sqrt_x as usize / 30 + 1;
// 篩
for i in 0..sqrt_xi {
let mut f = flags[i];
while f != 0 {
let ibit = Self::bit_to_index(f); // == if f == 0 { 0 } else { f.trailing_zeros() as usize };
let m = Self::MOD_30[ibit];
let pm = 30 * i + 2 * m;
let mut j = i * pm + (m * m) / 30;
let mut k = ibit;
let mask = Self::MASK[ibit];
let c0 = Self::C0[ibit];
while j < flags_size {
flags[j] &= mask[k];
j += i * Self::C1[k] as usize + c0[k] as usize;
k = (k + 1) % 8;
}
f &= f.wrapping_sub(1); // elase least one bit
}
}
// 結果出力
Self { x, flags }
}
/// エラトステネスの篩の高速化 (6) に近い実装
///
/// * <https://qiita.com/peria/items/c1d8523342e81bb23375>
///
/// (4)の省メモリ化・区間篩は未実装
pub fn generate_v6(x: u64) -> Self {
let flags_size = ((x / 30) as usize + if x % 30 != 0 { 1 } else { 0 }).max(1);
let (initial_loop, initial_size) = match x {
0..=209 => (0, 1),
210..=2309 => (1, 7),
2310..=30029 => (2, 7 * 11),
30030..=510509 => (3, 7 * 11 * 13),
510510..=9699689 => (4, 7 * 11 * 13 * 17),
_ => (5, 7 * 11 * 13 * 17 * 19),
};
assert!(flags_size >= initial_size);
// mod 30 == {1, 7, 11, 13, 17, 19, 23, 29} となるビット列 (mod 2,3,5 == 0 をあらかじめリストから除外)
// Rust 1.53.0 以降であれば、flagsを [`std::vec::Vec::with_capacity`] で作成してから 1要素だけ `255u8` を追加し、
// [`slice::copy_within`] の代わりに [`std::vec::Vec::extend_from_within`] でコピーする方が良さそう。
let mut flags = vec![0u8; flags_size];
flags[0] = !0u8;
// {7, 11, 13, 17, 19, 23} による篩
let mut size = 1;
for ibit in 1..=initial_loop {
let p = Self::MOD_30[ibit];
let nsize = size * p;
while size < nsize {
flags
.as_mut_slice()
.copy_within(0..(size.min(nsize - size)), size);
size = size.saturating_mul(2).min(nsize);
}
size = nsize;
let mut j = 0;
let mut k = 0;
let mask = Self::MASK[ibit];
let c0 = Self::C0[ibit];
while j < size {
flags[j] &= mask[k];
j += c0[k] as usize;
k = (k + 1) % 8;
}
}
// {7, 11, 13, 17, 19} による篩結果の繰り返しコピー
assert_eq!(size, initial_size);
while size < flags_size {
flags
.as_mut_slice()
.copy_within(0..(size.min(flags_size - size)), size);
size = size.saturating_add(size).min(flags_size);
}
assert_eq!(flags.len(), flags_size);
// {1} を篩から削除
assert_eq!(flags[0] & 1, 1);
flags[0] &= 0xfe;
assert_eq!(flags[0] & 1, 0);
// 末端の調整
flags[flags_size - 1] &= match x % 30 {
0..=0 => 0xff,
1..=6 => 0x01,
7..=10 => 0x03,
11..=12 => 0x07,
13..=16 => 0x0f,
17..=18 => 0x1f,
19..=22 => 0x3f,
23..=28 => 0x7f,
29..=29 => 0xff,
_ => unreachable!(),
};
// ceil(平方根),ceil(4乗根) の計算
let sqrt_x = sqrt_ceil(x);
let qurt_x = sqrt_ceil(sqrt_x);
let sqrt_xi = sqrt_x as usize / 30 + 1;
let qurt_xi = qurt_x as usize / 30 + 1;
// 初期篩(4乗根までの素数から2乗根までの素数を生成)
for i in 0..qurt_xi {
let mut f = flags[i];
while f != 0 {
let ibit = Self::bit_to_index(f); // == if f == 0 { 0 } else { f.trailing_zeros() as usize };
let m = Self::MOD_30[ibit];
let pm = 30 * i + 2 * m;
let mut j = i * pm + (m * m) / 30;
let mut k = ibit;
let mask = Self::MASK[ibit];
let c0 = Self::C0[ibit];
while j < sqrt_xi {
flags[j] &= mask[k];
j += i * Self::C1[k] as usize + c0[k] as usize;
k = (k + 1) % 8;
}
f &= f.wrapping_sub(1); // elase least one bit
}
}
// 区間篩用の篩位置リスト
let mut indecies = vec![0usize; sqrt_xi << 3];
for i in 0..sqrt_xi {
let mut f = flags[i];
while f != 0 {
let ibit = Self::bit_to_index(f); // == if f == 0 { 0 } else { f.trailing_zeros() as usize };
let iind = (i << 3) | ibit;
let m = Self::MOD_30[ibit];
let pm = 30 * i + 2 * m;
let j = i * pm + (m * m) / 30;
let k = ibit;
indecies[iind] = (j << 3) | k;
f &= f.wrapping_sub(1); // elase least one bit
}
}
// SEGMENT_SIZE毎に区間篩の繰り返し
// SEGMENT_SIZE毎に処理し、CPUのキャッシュミスによる遅延を減らす
for limit in
(Self::SEGMENT_SIZE..flags_size)
.step_by(Self::SEGMENT_SIZE)
.chain([flags_size].iter().cloned())
{
let sqrt_l = sqrt_floor(limit as u64 * 30);
let sqrt_li = sqrt_l as usize / 30 + 1;
for i in 0..sqrt_li {
invariant!(i < flags.len());
let mut f = flags[i];
while f != 0 {
let ibit = Self::bit_to_index(f); // == if f == 0 { 0 } else { f.trailing_zeros() as usize };
invariant!(ibit < Self::MASK.len());
let mask = &Self::MASK[ibit];
invariant!(ibit < Self::C0.len());
let c0 = &Self::C0[ibit];
let iind = (i << 3) | ibit;
invariant!(iind < indecies.len());
let mut j = indecies[iind] / 8;
let mut k = indecies[iind] % 8;
while k != 0 && j < limit {
invariant!(j < flags.len());
flags[j] &= mask[k]; j += i * Self::C1[k] as usize + c0[k] as usize;
k = (k + 1) % 8;
}
// loop unrolling
while j + i * 28 + Self::MOD_30[ibit] - 1 < limit {
invariant!(j < flags.len());
flags[j] &= mask[0]; j += i * Self::C1[0] as usize + c0[0] as usize;
invariant!(j < flags.len());
flags[j] &= mask[1]; j += i * Self::C1[1] as usize + c0[1] as usize;
invariant!(j < flags.len());
flags[j] &= mask[2]; j += i * Self::C1[2] as usize + c0[2] as usize;
invariant!(j < flags.len());
flags[j] &= mask[3]; j += i * Self::C1[3] as usize + c0[3] as usize;
invariant!(j < flags.len());
flags[j] &= mask[4]; j += i * Self::C1[4] as usize + c0[4] as usize;
invariant!(j < flags.len());
flags[j] &= mask[5]; j += i * Self::C1[5] as usize + c0[5] as usize;
invariant!(j < flags.len());
flags[j] &= mask[6]; j += i * Self::C1[6] as usize + c0[6] as usize;
invariant!(j < flags.len());
flags[j] &= mask[7]; j += i * Self::C1[7] as usize + c0[7] as usize;
}
while j < limit {
invariant!(j < flags.len());
flags[j] &= mask[k]; j += i * Self::C1[k] as usize + c0[k] as usize;
k = (k + 1) % 8;
}
invariant!(iind < indecies.len());
indecies[iind] = (j << 3) | k;
f &= f.wrapping_sub(1); // elase least one bit
}
}
}
// {7, 11, 13, 17, 19, 23, 29} を素数リストに追加
flags[0] = match x {
0..=6 => 0x00,
7..=10 => 0x02,
11..=12 => 0x06,
13..=16 => 0x0e,
17..=18 => 0x1e,
19..=22 => 0x3e,
23..=28 => 0x7e,
29..=29 => 0xfe,
_ => 0xfe,
};
// 結果出力
Self { x, flags }
}
fn _count(&self) -> u64 {
let mut count = match self.x {
0..=1 => 0, // count {}
2..=2 => 1, // count {2}
3..=4 => 2, // count {2, 3}
_ => 3, // count {2, 3, 5}
};
for &e in self.flags.iter() {
count += e.count_ones() as u64;
}
count
}
fn vec_primes_u32(&self) -> Vec<u32> {
assert_eq!(self.x >> 32, 0);
let mut result: Vec<u32> = vec![2, 3, 5];
result.reserve(approx_prime_pi(self.x) as usize);
for i in 0..self.flags.len() {
let mut f = self.flags[i];
while f != 0 {
let lsb = f & f.wrapping_neg(); // fetch least one bit
let ibit = Eratosthenes::bit_to_index(lsb);
let p = i as u32 * 30 + Eratosthenes::MOD_30[ibit] as u32;
result.push(p);
f &= f.wrapping_sub(1); // elase least one bit
}
}
result
}
fn _write_primes(&self, out: &mut dyn std::io::Write) {
for p in [2, 3, 5].iter().cloned().filter(|&p| p <= self.x) {
out.write_fmt(format_args!("{}\n", p)).unwrap();
}
for i in 0..self.flags.len() {
let mut f = self.flags[i];
while f != 0 {
let lsb = f & f.wrapping_neg(); // fetch least one bit
let ibit = Eratosthenes::bit_to_index(lsb);
let p = i as u64 * 30 + Eratosthenes::MOD_30[ibit] as u64;
out.write_fmt(format_args!("{}\n", p)).unwrap();
f &= f.wrapping_sub(1); // elase least one bit
}
}
out.flush().unwrap();
}
fn _write_last_primes(&self, out: &mut dyn std::io::Write) {
if let Some(i) = (0..self.flags.len()).rfind(|&i| self.flags[i] != 0) {
let mut f = self.flags[i];
while f != 0 {
let lsb = f & f.wrapping_neg(); // fetch least one bit
let ibit = Eratosthenes::bit_to_index(lsb);
let p = i as u64 * 30 + Eratosthenes::MOD_30[ibit] as u64;
out.write_fmt(format_args!("{}\n", p)).unwrap();
f &= f.wrapping_sub(1); // elase least one bit
}
}
out.flush().unwrap();
}
}
Submission Info
| Submission Time |
|
| Task |
D - AABCC |
| User |
mizarjp |
| Language |
Rust (1.42.0) |
| Score |
400 |
| Code Size |
127652 Byte |
| Status |
AC |
| Exec Time |
5 ms |
| Memory |
3036 KiB |
Judge Result
| Set Name |
Sample |
All |
| Score / Max Score |
0 / 0 |
400 / 400 |
| Status |
|
|
| Set Name |
Test Cases |
| Sample |
sample_01.txt, sample_02.txt |
| All |
sample_01.txt, sample_02.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt |
| Case Name |
Status |
Exec Time |
Memory |
| sample_01.txt |
AC |
5 ms |
2568 KiB |
| sample_02.txt |
AC |
3 ms |
2984 KiB |
| test_01.txt |
AC |
2 ms |
2464 KiB |
| test_02.txt |
AC |
2 ms |
2676 KiB |
| test_03.txt |
AC |
2 ms |
2668 KiB |
| test_04.txt |
AC |
3 ms |
2912 KiB |
| test_05.txt |
AC |
2 ms |
2960 KiB |
| test_06.txt |
AC |
2 ms |
2968 KiB |
| test_07.txt |
AC |
3 ms |
2960 KiB |
| test_08.txt |
AC |
2 ms |
2768 KiB |
| test_09.txt |
AC |
3 ms |
3036 KiB |
| test_10.txt |
AC |
2 ms |
2852 KiB |
| test_11.txt |
AC |
2 ms |
2800 KiB |
| test_12.txt |
AC |
2 ms |
2876 KiB |
| test_13.txt |
AC |
2 ms |
3036 KiB |
| test_14.txt |
AC |
4 ms |
2916 KiB |
| test_15.txt |
AC |
2 ms |
2844 KiB |