fn main() { input! { n: usize, m: usize, a: [usize; n], b: [usize; m], } if a[0] > 1 || b[0] > 1 { println!("1"); return; } let k = *a.iter().chain(b.iter()).max().unwrap(); let mut p = vec![false; k + 2]; let mut q = vec![false; k + 2]; for a in a.iter() { p[*a] = true; } for a in b.iter() { q[*a] = true; } let x = (1..).find(|x| !p[*x] && !q[*x]).unwrap(); let s = x * x; let mut val = (s..((x + 1).pow(2))).collect::>(); let mut divisor = vec![vec![1]; val.len()]; enumerate_prime(x, |p| { let mut k = (s + p - 1) / p * p - s; while k < val.len() { let div = &mut divisor[k]; let len = div.len(); while val[k] % p == 0 { val[k] /= p; for _ in 0..len { let v = div[div.len() - len] * p; div.push(v); } } k += p; } }); for (val, divisor) in val.iter().zip(divisor.iter_mut()) { if *val > 1 { let p = *val; for i in 0..divisor.len() { let v = divisor[i] * p; divisor.push(v); } } } let mut ans = 0; for (i, d) in divisor.iter().enumerate() { let mut can = false; let n = s + i; for d in d.iter() { let e = n / d; let a = kth_root(*d as u64, 2) as usize; let b = kth_root(e as u64, 2) as usize; if (p[a] && q[b]) || (p[b] && q[a]) { can = true; break; } } if !can { ans = n; break; } } println!("{}", ans); } // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 #[macro_export] macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- // ---------- begin miller-rabin ---------- fn is_prime_miller(n: u64) -> bool { if n <= 1 { return false; } else if n <= 3 { return true; } else if n % 2 == 0 { return false; } let pow = |r: u64, mut m: u64| -> u64 { let mut t = 1u128; let mut s = (r % n) as u128; let n = n as u128; while m > 0 { if m & 1 == 1 { t = t * s % n; } s = s * s % n; m >>= 1; } t as u64 }; let mut d = n - 1; let mut s = 0; while d % 2 == 0 { d /= 2; s += 1; } const B: [u64; 7] = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]; for &b in B.iter() { let mut a = pow(b, d); if a <= 1 { continue; } let mut i = 0; while i < s && a != n - 1 { i += 1; a = (a as u128 * a as u128 % n as u128) as u64; } if i >= s { return false; } } true } // ---------- end miller-rabin ---------- // ---------- begin enumerate prime ---------- fn enumerate_prime(n: usize, mut f: F) where F: FnMut(usize), { assert!(1 <= n && n <= 5 * 10usize.pow(8)); let batch = (n as f64).sqrt().ceil() as usize; let mut is_prime = vec![true; batch + 1]; for i in (2..).take_while(|p| p * p <= batch) { if is_prime[i] { let mut j = i * i; while let Some(p) = is_prime.get_mut(j) { *p = false; j += i; } } } let mut prime = vec![]; for (i, p) in is_prime.iter().enumerate().skip(2) { if *p && i <= n { f(i); prime.push(i); } } let mut l = batch + 1; while l <= n { let r = std::cmp::min(l + batch, n + 1); is_prime.clear(); is_prime.resize(r - l, true); for &p in prime.iter() { let mut j = (l + p - 1) / p * p - l; while let Some(is_prime) = is_prime.get_mut(j) { *is_prime = false; j += p; } } for (i, _) in is_prime.iter().enumerate().filter(|p| *p.1) { f(i + l); } l += batch; } } // ---------- end enumerate prime ---------- // floor(a ^ (1 / k)) pub fn kth_root(a: u64, k: u64) -> u64 { assert!(k > 0); if a == 0 { return 0; } if k >= 64 { return 1; } if k == 1 { return a; } let valid = |x: u64| -> bool { let mut t = x; for _ in 1..k { let (val, ok) = t.overflowing_mul(x); if !(!ok && val <= a) { return false; } t = val; } true }; let mut ok = 1; let mut ng = 2; while valid(ng) { ok = ng; ng *= 2; } while ng - ok > 1 { let mid = ok + (ng - ok) / 2; if valid(mid) { ok = mid; } else { ng = mid; } } ok }