#692301 (Rust) No.1653 Squarefree

• 問題: No.1653 Squarefree
• ユーザー: cotton_fn_
• 提出日時: 2021-08-25 19:32:33
• 言語: Rust (1.83.0 + proconio)
• 結果: WA
• 実行時間: -
• コード長: 9,484 bytes
• コンパイル時間: 12,860 ms
• コンパイル使用メモリ: 378,020 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-17 02:11:43
• 合計ジャッジ時間: 19,885 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 32 WA * 6

ソースコード

#![allow(unused_imports)]
use pio2::*;
use std::{
    collections::*,
    io::{self, prelude::*},
};
fn run<I: Input, O: Write>(mut pin: I, mut out: O) {
    let (l, r): (usize, usize) = pin.parse();
    let r = r + 1;
    let mut tab = vec![false; r - l];
    for i in 2..=1000000 {
        let s = i * i;
        let t = (l + s - 1) / s * s - l;
        for j in (t..r - l).step_by(s) {
            tab[j] = true;
        }
    }
    for i in 2..=1000000 {
        for j in ((l + i - 1) / i * i..r).step_by(i) {
            debug_assert_eq!(j % i, 0);
            if !tab[j - l] {
                let q = j / i;
                let r = (q as f64).sqrt().round() as usize;
                if r * r == j {
                    tab[j - l] = true;
                }
            }
        }
    }
    let ans = tab.iter().filter(|f| !*f).count();
    wln!(out, "{}", ans);
}
fn main() {
    let stdin = io::stdin();
    let mut pin = Scanner::new(stdin.lock());
    let stdout = io::stdout();
    let mut out = stdout.lock();
    run(&mut pin, &mut out);
}
pub mod macros {
    #[macro_export]
    macro_rules ! w { ($ ($ arg : tt) *) => { write ! ($ ($ arg) *) . unwrap () ; } }
    #[macro_export]
    macro_rules ! wln { ($ dst : expr $ (, $ ($ arg : tt) *) ?) => { { writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; # [cfg (debug_assertions)] $ dst . flush () . unwrap () ; } } }
    #[macro_export]
    macro_rules! w_iter {
        ($dst:expr, $fmt:expr, $iter:expr, $delim:expr) => {{
            let mut first = true;
            for elem in $iter {
                if first {
                    w!($dst, $fmt, elem);
                    first = false;
                } else {
                    w!($dst, concat!($delim, $fmt), elem);
                }
            }
        }};
        ($dst:expr, $fmt:expr, $iter:expr) => {
            w_iter!($dst, $fmt, $iter, " ")
        };
    }
    #[macro_export]
    macro_rules ! w_iter_ln { ($ dst : expr , $ ($ t : tt) *) => { { w_iter ! ($ dst , $ ($ t) *) ; wln ! ($ dst) ; } } }
    #[macro_export]
    macro_rules ! e { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprint ! ($ ($ t) *) } }
    #[macro_export]
    macro_rules ! eln { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprintln ! ($ ($ t) *) } }
    #[macro_export]
    macro_rules ! __tstr { ($ h : expr $ (, $ t : expr) +) => { concat ! (__tstr ! ($ ($ t) ,+) , ", " , __tstr ! (@)) } ; ($ h : expr) => { concat ! (__tstr ! () , " " , __tstr ! (@)) } ; () => { "\x1B[94m[{}:{}]\x1B[0m" } ; (@) => { "\x1B[1;92m{}\x1B[0m = {:?}" } }
    #[macro_export]
    macro_rules ! d { ($ ($ a : expr) ,*) => { eln ! (__tstr ! ($ ($ a) ,*) , file ! () , line ! () , $ (stringify ! ($ a) , $ a) ,*) } ; }
}
pub mod pio2 {
    use std::{
        io::prelude::*,
        marker::PhantomData,
        mem::{self, MaybeUninit},
        str,
    };
    pub trait Input {
        fn bytes(&mut self) -> &[u8];
        #[inline]
        fn str(&mut self) -> &str {
            str::from_utf8(self.bytes()).unwrap()
        }
        #[inline]
        fn parse<T>(&mut self) -> T
        where
            DefaultParser: Parser<T>,
        {
            self.parse_with(DefaultParser)
        }
        #[inline]
        fn parse_with<T, P: Parser<T>>(&mut self, mut parser: P) -> T {
            parser.parse(self)
        }
        #[inline]
        fn seq<T>(&mut self, n: usize) -> Seq<Self, T, DefaultParser>
        where
            DefaultParser: Parser<T>,
        {
            self.seq_with(n, DefaultParser)
        }
        #[inline]
        fn seq_with<T, P: Parser<T>>(&mut self, n: usize, parser: P) -> Seq<Self, T, P> {
            Seq {
                src: self,
                rest: n,
                parser,
                phantom: PhantomData,
            }
        }
    }
    impl<I: Input> Input for &mut I {
        #[inline]
        fn bytes(&mut self) -> &[u8] {
            (**self).bytes()
        }
    }
    pub struct Scanner<R> {
        src: R,
        buf: Vec<u8>,
        pos: usize,
        len: usize,
    }
    impl<R: Read> Scanner<R> {
        #[inline]
        pub fn new(src: R) -> Self {
            Self {
                src,
                buf: vec![0; 1 << 16],
                pos: 0,
                len: 0,
            }
        }
        fn read(&mut self) -> usize {
            if self.pos > 0 {
                self.buf.copy_within(self.pos..self.len, 0);
                self.len -= self.pos;
                self.pos = 0;
            } else if self.len >= self.buf.len() {
                self.buf.resize(2 * self.buf.len(), 0);
            }
            let n = self.src.read(&mut self.buf[self.len..]).unwrap();
            self.len += n;
            assert!(self.len <= self.buf.len());
            n
        }
    }
    impl<R: Read> Input for Scanner<R> {
        fn bytes(&mut self) -> &[u8] {
            loop {
                while let Some(d) = unsafe { self.buf.get_unchecked(self.pos..self.len) }
                    .iter()
                    .position(u8::is_ascii_whitespace)
                {
                    let p = self.pos;
                    self.pos += d + 1;
                    if d > 0 {
                        return unsafe { self.buf.get_unchecked(p..p + d) };
                    }
                }
                if self.read() == 0 {
                    let p = self.pos;
                    if p == self.len {
                        panic!("reached EOF");
                    }
                    self.pos = self.len;
                    return unsafe { self.buf.get_unchecked(p..self.len) };
                }
            }
        }
    }
    pub struct Seq<'a, I: ?Sized, T, P> {
        src: &'a mut I,
        rest: usize,
        parser: P,
        phantom: PhantomData<*const T>,
    }
    impl<'a, I: Input + ?Sized, T, P: Parser<T>> Iterator for Seq<'a, I, T, P> {
        type Item = T;
        #[inline]
        fn next(&mut self) -> Option<T> {
            if self.rest > 0 {
                self.rest -= 1;
                Some(self.src.parse_with(&mut self.parser))
            } else {
                None
            }
        }
        #[inline]
        fn size_hint(&self) -> (usize, Option<usize>) {
            (self.rest, Some(self.rest))
        }
    }
    impl<'a, I: Input + ?Sized, T, P: Parser<T>> ExactSizeIterator for Seq<'a, I, T, P> {}
    pub trait Parser<T> {
        fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> T;
    }
    impl<T, P: Parser<T>> Parser<T> for &mut P {
        #[inline]
        fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> T {
            (*self).parse(src)
        }
    }
    #[derive(Clone, Copy, Debug)]
    pub struct DefaultParser;
    macro_rules ! impls { ($ m : ident , $ ($ ty : ty) ,*) => { $ ($ m ! ($ ty) ;) * } ; }
    macro_rules! int {
        ($ty:ty) => {
            impl Parser<$ty> for DefaultParser {
                #[inline]
                fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {
                    let f = |s: &[u8]| s.iter().fold(0, |x, b| 10 * x + (b & 0xf) as $ty);
                    let s = src.bytes();
                    if let Some((&b'-', t)) = s.split_first() {
                        -f(t)
                    } else {
                        f(s)
                    }
                }
            }
        };
    }
    impls!(int, isize, i8, i16, i32, i64, i128);
    macro_rules! uint {
        ($ty:ty) => {
            impl Parser<$ty> for DefaultParser {
                #[inline]
                fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {
                    src.bytes().iter().fold(0, |x, b| 10 * x + (b & 0xf) as $ty)
                }
            }
        };
    }
    impls!(uint, usize, u8, u16, u32, u64, u128);
    macro_rules! from_bytes {
        ($ty:ty) => {
            impl Parser<$ty> for DefaultParser {
                #[inline]
                fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {
                    src.bytes().into()
                }
            }
        };
    }
    impls!(from_bytes, Vec<u8>, Box<[u8]>);
    macro_rules! from_str {
        ($ty:ty) => {
            impl Parser<$ty> for DefaultParser {
                #[inline]
                fn parse<I: Input + ?Sized>(&mut self, src: &mut I) -> $ty {
                    src.str().parse::<$ty>().expect("failed to parse")
                }
            }
        };
    }
    impls!(from_str, String, char, f32, f64);
    macro_rules ! tuple { ($ ($ T : ident) ,+) => { impl <$ ($ T) ,+> Parser < ($ ($ T ,) +) > for DefaultParser where $ (DefaultParser : Parser <$ T >) ,+ { # [inline] fn parse < I : Input + ? Sized > (& mut self , src : & mut I) -> ($ ($ T ,) +) { ($ (< Self as Parser <$ T >>:: parse (self , src) ,) +) } } } ; }
    tuple!(A);
    tuple!(A, B);
    tuple!(A, B, C);
    tuple!(A, B, C, D);
    tuple!(A, B, C, D, E);
    tuple!(A, B, C, D, E, F);
    tuple!(A, B, C, D, E, F, G);
    tuple!(A, B, C, D, E, F, G, H);
    macro_rules ! array { ($ ($ N : literal) *) => { $ (impl < T > Parser < [T ; $ N] > for DefaultParser where DefaultParser : Parser < T > { fn parse < I : Input + ? Sized > (& mut self , src : & mut I) -> [T ; $ N] { unsafe { let mut arr : [MaybeUninit < T >; $ N] = MaybeUninit :: uninit () . assume_init () ; for elem in & mut arr { * elem = MaybeUninit :: new (src . parse ()) ; } mem :: transmute_copy (& arr) } } }) * } }
    array ! (1 2 3 4 5 6 7 8);
}