結果

問題 No.1463 Hungry Kanten
ユーザー RheoTommyRheoTommy
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![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/RheoTommy
use 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 {
/// ni
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<_>>()
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0