// -*- coding:utf-8-unix -*- #![allow(dead_code)] #![allow(unused_imports)] use std::cmp::Ordering::*; use std::collections::*; use std::convert::*; use std::convert::{From, Into}; use std::fmt::Debug; use std::fs::File; use std::io::prelude::*; use std::io::*; use std::marker::Copy; use std::mem::*; use std::ops::Bound::*; use std::ops::{Add, Mul, Neg, Sub}; use std::str; use std::vec; use std::{cmp, process::Output}; use std::{cmp::Ordering, env::consts::DLL_PREFIX}; const INF: i64 = 1223372036854775807; const MEM_SIZE: usize = 202020; const MOD: i64 = 1000000007; // const MOD: i64 = 998244353; use std::cmp::*; use std::collections::*; use std::io::stdin; use std::io::stdout; use std::io::Write; use btree_map::{Keys, Values}; // use str::Chars; #[allow(dead_code)] fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } #[allow(dead_code)] fn readi() -> (i64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); iter.next().unwrap().parse::().unwrap() } #[allow(dead_code)] fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[allow(dead_code)] fn read_vec2(n: u32) -> Vec> { (0..n).map(|_| read_vec()).collect() } #[allow(dead_code)] fn readii() -> (i64, i64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } fn readff() -> (f64, f64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } #[allow(dead_code)] fn readiii() -> (i64, i64, i64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } #[allow(dead_code)] fn readuu() -> (usize, usize) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } fn readcc() -> (char, char) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } #[allow(dead_code)] fn readuuu() -> (usize, usize, usize) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } #[allow(dead_code)] fn readuuuu() -> (usize, usize, usize, usize) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } fn readiiii() -> (i64, i64, i64, i64) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } #[derive(PartialEq, PartialOrd, Clone, Copy, Debug)] struct F64Total(f64); impl Eq for F64Total {} impl Ord for F64Total { fn cmp(&self, other: &F64Total) -> Ordering { let F64Total(f1) = *self; let F64Total(f2) = *other; if f1.is_nan() { Less } else if f2.is_nan() { Greater } else { if (f1 - f2).is_sign_positive() { Greater } else { Less } } } } fn readin() -> (usize, char) { let mut str = String::new(); let _ = stdin().read_line(&mut str).unwrap(); let mut iter = str.split_whitespace(); ( iter.next().unwrap().parse::().unwrap(), iter.next().unwrap().parse::().unwrap(), ) } fn solve() { let (n, m, p) = readuuu(); let vec: Vec = read_vec(); let mut data = vec![(F64Total(0.0), 0, 0); n]; for i in 0..n { let mut cnt = 1 as usize; let mut x = vec[i]; while x % p == 0 { cnt += 1; x /= p; } data[i].2 = x; data[i].1 = cnt; let mut r = F64Total(data[i].2 as f64 / data[i].1 as f64); data[i].0 = r; } data.sort(); data.reverse(); while !data.is_empty() { let mut x = *data.last().unwrap(); let x = x.2; if x == 1 { data.pop(); } else { break; } } if data.is_empty() { println!("{:?}", -1); return; } // data.reverse(); // println!("{:?}", data); for i in 0..data.len() { let x = data[i].1; data[i].1 = data[i].2; data[i].2 = x; } let mut rres = 0; let mut mm = m; while mm > 0 { mm /= data[0].1; rres += data[0].2; } rres -= 1; let mut res = INF as usize; let mut p = data[0].1.pow(rres as u32); // println!("{:?}", p); if p < m { for &x in data.iter() { if p * x.1 >= m { res = min(res, rres + x.2); } } } else { res = rres; } println!("{:?}", res); return; } fn main() { solve() }