#566336 (Rust) No.811 約数の個数の最大化

• 問題: No.811 約数の個数の最大化
• ユーザー: manta1130
• 提出日時: 2020-10-13 18:38:25
• 言語: Rust (1.77.0)
• 結果: WA
• 実行時間: -
• コード長: 5,905 bytes
• コンパイル時間: 2,640 ms
• コンパイル使用メモリ: 170,880 KB
• 実行使用メモリ: 4,500 KB
• 最終ジャッジ日時: 2023-09-28 00:13:25
• 合計ジャッジ時間: 3,320 ms
• ジャッジサーバーID （参考情報）: judge14 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	1 ms; 4,376 KB
testcase_02	AC	2 ms; 4,376 KB
testcase_03	AC	1 ms; 4,380 KB
testcase_04	AC	0 ms; 4,380 KB
testcase_05	WA	-
testcase_06	WA	-
testcase_07	AC	1 ms; 4,376 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	AC	1 ms; 4,376 KB

コンパイルメッセージ

warning: unused attribute `macro_export`
  --> Main.rs:70:5
   |
70 |     #[macro_export]
   |     ^^^^^^^^^^^^^^^
   |
note: the built-in attribute `macro_export` will be ignored, since it's applied to the macro invocation `thread_local`
  --> Main.rs:71:5
   |
71 |     thread_local! {
   |     ^^^^^^^^^^^^
   = note: `#[warn(unused_attributes)]` on by default

warning: unused variable: `q`
  --> Main.rs:43:19
   |
43 |         .filter(|(q, w)| ans * *w < n)
   |                   ^ help: if this is intentional, prefix it with an underscore: `_q`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: 2 warnings emitted

ソースコード

use std::collections::{BTreeMap, BTreeSet};
fn main() {
    inputv! {
        n:usize,k:usize
    }
    let mut m = BTreeMap::new();
    let mut s = BTreeSet::new();
    for x in PrimeFactorization::calc(n) {
        *m.entry(x).or_insert(0) += 1;
    }
    let mut ans = 1;
    let mut ans_p = BTreeMap::new();
    let mut q = 0;
    while q < k {
        for (&i, x) in m.iter_mut() {
            if *x == 0 {
                continue;
            }
            ans *= i;
            *ans_p.entry(i).or_insert(0) += 1;
            *x -= 1;
            s.insert(i);
            q += 1;
            if q >= k {
                break;
            }
        }
    }
    let pl = get_primelist(n);
    for i in pl {
        if s.contains(&i) {
            continue;
        }
        if ans * i >= n {
            break;
        }
        *ans_p.entry(i).or_insert(0) += 1;
        ans *= i;
    }
    let mut ans_p = ans_p
        .iter()
        .map(|(q, w)| (*w, *q))
        .filter(|(q, w)| ans * *w < n)
        .collect::<Vec<_>>();
    ans_p.sort();

    let mut flag = false;
    while !flag {
        flag = true;
        for (i, x) in ans_p.iter_mut() {
            if *x * ans < n {
                *i += 1;
                ans *= *x;
                flag = false;
            }
        }
    }

    println!("{}", ans);
}

//https://github.com/manta1130/competitive-template-rs

pub mod input {
    use std::cell::RefCell;
    use std::io;
    pub const SPLIT_DELIMITER: char = ' ';
    pub use std::io::prelude::*;

    #[macro_export]
    thread_local! {
        pub static INPUT_BUFFER:RefCell<std::collections::VecDeque<String>>=RefCell::new(std::collections::VecDeque::new());
    }

    #[macro_export]
    macro_rules! inputv {
    ( $($x:ident : $t:ty),*) => {
                $(
                INPUT_BUFFER.with(|p| if p.borrow().len()==0{
                    let temp_str = input_line_str();
                    let mut split_result_iter = temp_str.split(SPLIT_DELIMITER).map(|q|q.to_string()).collect::<std::collections::VecDeque<_>>();
                    p.borrow_mut().append(&mut split_result_iter)
                });
                let mut buf_split_result=String::new();
                INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
                    let $x:$t = buf_split_result.parse().unwrap();
                )*
    };
}

    #[macro_export]
    macro_rules! input_all {
    ( $($x:ident : $t:ty),*) => {
                $(
                INPUT_BUFFER.with(|p| if p.borrow().len()==0{
                    let mut temp_str = String::new();
                    std::io::stdin().read_to_string(&mut temp_str).unwrap();
                    let mut split_result_iter = temp_str.split_whitespace().map(|q|q.to_string()).collect::<std::collections::VecDeque<_>>();
                    p.borrow_mut().append(&mut split_result_iter)
                });
                let mut buf_split_result=String::new();
                INPUT_BUFFER.with(|p| buf_split_result = p.borrow_mut().pop_front().unwrap());
                    let ($x):($t) = buf_split_result.parse().unwrap();
                )*
    };
}

    pub fn input_line_str() -> String {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        s.trim().to_string()
    }

    #[allow(clippy::match_wild_err_arm)]
    pub fn input_vector<T>() -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v: Vec<T> = Vec::new();

        let s = input_line_str();
        let split_result = s.split(SPLIT_DELIMITER);
        for z in split_result {
            let buf = match z.parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error",),
            };
            v.push(buf);
        }
        v
    }

    #[allow(clippy::match_wild_err_arm)]
    pub fn input_vector_row<T>(n: usize) -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v = Vec::with_capacity(n);
        for _ in 0..n {
            let buf = match input_line_str().parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error",),
            };
            v.push(buf);
        }
        v
    }

    pub trait ToCharVec {
        fn to_charvec(&self) -> Vec<char>;
    }

    impl ToCharVec for String {
        fn to_charvec(&self) -> Vec<char> {
            self.to_string().chars().collect::<Vec<_>>()
        }
    }
}
pub mod primenumber {
    use std::iter::Iterator;

    type ValueType = usize;

    pub struct PrimeFactorization {
        n: ValueType,
        cur: ValueType,
    }

    impl PrimeFactorization {
        pub fn calc(n: ValueType) -> PrimeFactorization {
            PrimeFactorization { n, cur: 1 }
        }
    }

    impl Iterator for PrimeFactorization {
        type Item = ValueType;
        fn next(&mut self) -> Option<Self::Item> {
            loop {
                if self.cur == 0 || self.cur > self.n {
                    return None;
                }

                self.cur += 1;

                if self.cur * self.cur > self.n {
                    if self.n != 1 {
                        self.cur = 0;
                        return Some(self.n);
                    }
                    return None;
                }
                if self.n % self.cur == 0 {
                    self.n /= self.cur;
                    self.cur -= 1;
                    return Some(self.cur + 1);
                }
            }
        }
    }

    pub fn get_primelist(u: usize) -> Vec<usize> {
        let mut v = vec![true; u + 1];
        let mut r = vec![];
        for i in 2..=u {
            if v[i] {
                r.push(i);
                let mut j = i * 2;
                while j <= u {
                    v[j] = false;
                    j += i;
                }
            }
        }
        r
    }
}
use input::*;
use primenumber::*;