#![allow(unused_imports, dead_code, unused_macros, unused_variables, non_snake_case, unused_parens)] use std::cmp::*; use std::mem::swap; use std::collections::*; const MOD:u64 = 1_000_000_007; const INF:i64 = 0x7fff_ffff_ffff_ffff; macro_rules! min {($a:expr $(,)*) => {{$a}};($a:expr, $b:expr $(,)*) => {{std::cmp::min($a, $b)}};($a:expr, $($rest:expr),+ $(,)*) => {{std::cmp::min($a, min!($($rest),+))}};} macro_rules! max {($a:expr $(,)*) => {{$a}};($a:expr, $b:expr $(,)*) => {{std::cmp::max($a, $b)}};($a:expr, $($rest:expr),+ $(,)*) => {{std::cmp::max($a, max!($($rest),+))}};} macro_rules! mulvec {($x:expr; $s:expr) => {vec![$x; $s]};($x:expr; $s0:expr; $( $s:expr );+) => {mulvec![vec![$x; $s0]; $( $s );+ ]};} fn solve() { input! { n:usize, k:u64, A:[u64;n], } let k_fac = Factorization::prime_factor(k); let mut kf = vec![]; for (k,v) in k_fac { kf.push(k*v as u64); } for a in A { let mut tmp = vec![]; for x in kf { if a % x != 0 { tmp.push(x); } } kf = tmp; } println!("{}", if kf.is_empty() {"Yes"}else{"No"}); } use std::ops::*; pub fn gcd(mut a: T, mut b: T) -> T where T: Copy + Default + PartialOrd + Rem { if a < b { let tmp = a; a = b; b = tmp; } while b != T::default() { let (ta,tb) = (b, a%b); a = ta; b = tb; } a } fn main() { std::thread::Builder::new() .stack_size(128 * 1024 * 1024) .spawn(|| solve()).unwrap() .join().unwrap(); } mod _input { // https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); let mut next = || { iter.next().unwrap() }; input_inner!{next, $($r)*} }; ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes .by_ref() .map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } #[macro_export] macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::>() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; } } pub struct Factorization; impl Factorization { fn gcd(mut a: u64, mut b: u64) -> u64 { while b != 0 { let tmp = b; b = a%b; a = tmp; } a } #[inline] fn mul_mod(a:u64, b:u64, m:u64) -> u64 { ((a as u128 * b as u128) % m as u128) as u64 } #[inline] fn mul_add_mod(a:u64, b:u64, c:u64, m:u64) -> u64 { ((a as u128 * b as u128 + c as u128) % m as u128) as u64 } fn pow_mod(x: u64, mut n: u64, m: u64) -> u64 { if m == 1 { return 0; } let mut r: u64 = 1; let mut y: u64 = x.rem_euclid(m); while n != 0 { if (n & 1) > 0 { r = Self::mul_mod(r, y, m); } y = Self::mul_mod(y, y, m); n >>= 1; } r } fn is_prime_mr(n: u64) -> bool { let mut d = n - 1; d /= d & d.wrapping_neg(); let l = [2_u64, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]; for &a in l.iter() { let mut t = d; let mut y = Self::pow_mod(a, t, n); if y == 1 { continue; } while y != n - 1 { y = Self::mul_mod(y, y, n); if y == 1 || t == n - 1 { return false; } t <<= 1; } } true } fn find_factor_rho(n: u64) -> u64 { let m = 1 << ((n as f64).log2() as u64 / 8); for c in 1..99 { let f = |x: u64| -> u64 { Self::mul_add_mod(x, x, c, n) }; let mut y = 2; let mut r = 1_u64; let mut q = 1; let mut g = 1; let mut ys = 0; let mut x = 0; while g == 1 { x = y; for _ in 0..r { y = f(y); } let mut k = 0; while k < r && g == 1 { ys = y; for _ in 0..m.min(r - k) { y = f(y); q = Self::mul_mod(q, (x as i64 - y as i64).abs() as u64, n); } g = Self::gcd(q, n); k += m; } r <<= 1; } if g == n { g = 1; while g == 1 { ys = f(ys); g = Self::gcd((x as i64 - ys as i64).abs() as u64, n); } } if g < n { if Self::is_prime_mr(g) { return g; } else if Self::is_prime_mr(n / g) { return n / g; } else { return Self::find_factor_rho(g); } } } unreachable!() } pub fn prime_factor(mut n: u64) -> HashMap { let mut ret: HashMap = HashMap::new(); let mut i = 2; while i * i <= n { let mut k = 0; while n % i == 0 { n /= i; k += 1; } if k > 0 { ret.insert(i, k); } i += if i % 2 == 0 { 1 } else { 2 }; if i == 101 && n >= (1 << 20) { while n > 1 { if Self::is_prime_mr(n) { ret.insert(n, 1); break; } else { let j = Self::find_factor_rho(n); let mut k = 0; while n % j == 0 { n /= j; k += 1; } ret.insert(j, k); } } } } if n > 1 { ret.insert(n, 1); } ret } }