結果
問題 | No.2244 Integer Complete |
ユーザー |
![]() |
提出日時 | 2023-03-10 21:59:45 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 6,319 bytes |
コンパイル時間 | 13,964 ms |
コンパイル使用メモリ | 382,936 KB |
実行使用メモリ | 19,584 KB |
最終ジャッジ日時 | 2024-09-18 04:16:30 |
合計ジャッジ時間 | 15,633 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 60 |
コンパイルメッセージ
warning: function `is_prime_miller` is never used --> src/main.rs:124:4 | 124 | fn is_prime_miller(n: u64) -> bool { | ^^^^^^^^^^^^^^^ | = note: `#[warn(dead_code)]` on by default
ソースコード
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::<Vec<_>>();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::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, bytes) => {read_value!($iter, String).bytes().collect::<Vec<u8>>()};($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<F>(n: usize, mut f: F)whereF: 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}