結果
問題 | No.1463 Hungry Kanten |
ユーザー |
![]() |
提出日時 | 2021-04-02 22:33:26 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1,379 ms / 2,000 ms |
コード長 | 6,407 bytes |
コンパイル時間 | 15,571 ms |
コンパイル使用メモリ | 378,812 KB |
実行使用メモリ | 100,864 KB |
最終ジャッジ日時 | 2024-12-23 23:38:18 |
合計ジャッジ時間 | 20,529 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#![allow(unused_macros)]#![allow(dead_code)]#![allow(unused_imports)]// # ファイル構成// - use 宣言// - lib モジュール// - main 関数// - basic モジュール//// 常に使うテンプレートライブラリは basic モジュール内にあります。// 問題に応じて使うライブラリ lib モジュール内にコピペしています。// ライブラリのコードはこちら → https://github.com/RheoTommy/at_coder// Twitter はこちら → https://twitter.com/RheoTommyuse std::collections::*;use std::io::{stdout, BufWriter, Write};use crate::basic::*;use crate::lib::*;pub mod lib {/// 構築O(N log log N)で素因数分解系の操作が高速に行えるpub struct Eratosthenes {/// n以下の整数iを割り切る最小の素数min_prime: Vec<usize>,}impl Eratosthenes {/// 構築O(N log log N)pub fn new(n: usize) -> Self {let mut min_prime = (0..=n).collect::<Vec<_>>();let mut i = 2usize;while i * i <= n {if min_prime[i] == i {let mut j = 1;while i * j <= n {if min_prime[i * j] == i * j {min_prime[i * j] = i;}j += 1;}}i += 1;}Self { min_prime }}/// 素数判定O(1)pub fn is_prime(&self, i: usize) -> bool {if i <= 1 {return false;}self.min_prime[i] == i}/// 素因数分解O(log N)pub fn factorization(&self, i: usize) -> std::collections::HashMap<usize, usize> {assert_ne!(i, 0);let mut map = std::collections::HashMap::new();let mut now = i;while now != 1 {let p = self.min_prime[now];*map.entry(p).or_insert(0) += 1;now /= p;}map}/// 最大公約数O((log N)^2)pub fn gcd(&self, i: usize, j: usize) -> std::collections::HashMap<usize, usize> {assert_ne!(i, 0);assert_ne!(j, 0);let mut map = std::collections::HashMap::new();let im = self.factorization(i);let jm = self.factorization(j);for (k, v) in im {if jm.contains_key(&k) {map.insert(k, v.min(jm[&k]));}}map}/// 最小公倍数O((log N)^2)pub fn lcm(&self, i: usize, j: usize) -> std::collections::HashMap<usize, usize> {assert_ne!(i, 0);assert_ne!(j, 0);let mut map = std::collections::HashMap::new();let im = self.factorization(i);let jm = self.factorization(j);for (&k, &v) in &im {if jm.contains_key(&k) {map.insert(k, v.max(jm[&k]));} else {map.insert(k, v);}}for (k, v) in jm {if !im.contains_key(&k) {map.insert(k, v);}}map}}}fn main() {let mut sc = Scanner::new();let n = sc.next_usize();let k = sc.next_usize();let a = sc.next_vec(n);let era = Eratosthenes::new(2 * 100000);let mut v = vec![];for bit in 0usize..1 << n {if bit.count_ones() < k as u32 {continue;}let mut sum = 0;let mut mul = HashMap::new();for i in 0..n {if bit >> i & 1 == 1 {sum += a[i];for (k, v) in era.factorization(a[i]) {*mul.entry(k).or_insert(0) += v;}}}let mut mul = mul.into_iter().collect::<Vec<_>>();mul.sort();let mut sum = era.factorization(sum).into_iter().collect::<Vec<_>>();sum.sort();v.push(mul);v.push(sum);}v.sort();v.dedup();println!("{}", v.len());}pub mod basic {pub const U_INF: u64 = (1 << 60) + (1 << 30);pub const I_INF: i64 = (1 << 60) + (1 << 30);pub struct Scanner {buf: std::collections::VecDeque<String>,reader: std::io::BufReader<std::io::Stdin>,}impl Scanner {pub fn new() -> Self {Self {buf: std::collections::VecDeque::new(),reader: std::io::BufReader::new(std::io::stdin()),}}fn scan_line(&mut self) {use std::io::BufRead;let mut flag = 0;while self.buf.is_empty() {let mut s = String::new();self.reader.read_line(&mut s).unwrap();let mut iter = s.split_whitespace().peekable();if iter.peek().is_none() {if flag >= 5 {panic!("There is no input!");}flag += 1;continue;}for si in iter {self.buf.push_back(si.to_string());}}}pub fn next<T: std::str::FromStr>(&mut self) -> T {self.scan_line();self.buf.pop_front().unwrap().parse().unwrap_or_else(|_| panic!("Couldn't parse!"))}pub fn next_usize(&mut self) -> usize {self.next()}pub fn next_int(&mut self) -> i64 {self.next()}pub fn next_uint(&mut self) -> u64 {self.next()}pub fn next_chars(&mut self) -> Vec<char> {self.next::<String>().chars().collect()}pub fn next_string(&mut self) -> String {self.next()}pub fn next_char(&mut self) -> char {self.next()}pub fn next_float(&mut self) -> f64 {self.next()}pub fn next_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {(0..n).map(|_| self.next()).collect::<Vec<_>>()}}}