struct Scanner { r: R, buf: Vec } impl Scanner { fn new(r: R) -> Scanner { Scanner { r, buf: Vec::with_capacity(8000) } } fn next(&mut self) -> &str { self.buf.clear(); loop { let (done, used) = { let available = self.r.fill_buf().unwrap(); match available.iter().position(|b| !b.is_ascii_whitespace()) { Some(i) => (true, i), None => (false, available.len()), } }; self.r.consume(used); if done || used == 0 { break; } } loop { let (done, used) = { let available = self.r.fill_buf().unwrap(); match available.iter().position(|b| b.is_ascii_whitespace()) { Some(i) => { self.buf.extend_from_slice(&available[..i]); (true, i) } None => { self.buf.extend_from_slice(&available); (false, available.len()) } } }; self.r.consume(used); if done || used == 0 { unsafe { return std::str::from_utf8_unchecked(&self.buf); } } } } } macro_rules! parse { ($s:expr, Chars) => ($s.chars().collect::>()); ($s:expr, Bytes) => ($s.bytes().collect::>()); ($s:expr, Usize1) => (parse!($s, usize) - 1); ($s:expr, $t:ty) => ($s.parse::<$t>().unwrap()); } macro_rules! read { ($sc:expr, [$t:tt; $n:expr]) => ( (0..$n).map(|_| read!($sc, $t)).collect::>() ); ($sc:expr, ($($t:tt),*)) => (($(read!($sc, $t)),*)); ($sc:expr, $t:ident) => (parse!($sc.next(), $t)); ($sc:expr, $($t:tt),*) => (($(read!($sc, $t)),*)); } fn main() { use std::io::Write; let (stdin, stdout) = (std::io::stdin(), std::io::stdout()); let mut sc = Scanner::new(stdin.lock()); let mut wr = std::io::BufWriter::new(stdout.lock()); macro_rules! scan { ($($t:tt)*) => (read!(sc, $($t)*)); } macro_rules! println { ($($arg:tt)*) => (writeln!(wr, $($arg)*).ok()); } let (n, m, p) = scan!(usize, usize, usize); let a = scan!([usize; n]); let max_a = a.iter().max().unwrap(); if m < *max_a { println!("1"); return; } let m = m / max_a; let mut b = Vec::with_capacity(n); for mut a in a { let mut c: usize = 1; while a % p == 0 { a /= p; c += 1; } if a == 1 { continue; } b.push((c, a)); } b.sort_by_key(|key| (key.0, std::cmp::Reverse(key.1))); let mut v = Vec::new(); let mut max_a = 0; for (c, a) in b { if a <= max_a { continue; } v.push((c, a)); max_a = max_a.max(a); } let mut ans = std::usize::MAX; let mut map = std::collections::BTreeMap::new(); map.insert(0, 1); for cost in 0.. { if let Some(&x) = map.get(&cost) { for (c, a) in &v { let next_cost = cost + c; let next_x = x * a; if next_x > m { ans = ans.min(next_cost + 1); } else { let value = map.entry(next_cost).or_default(); *value = std::cmp::max(*value, next_x); } } map.remove(&cost); if map.is_empty() { break; } } } println!("{}", ans as isize); }