#962606 (Rust) No.2682 Visible Divisible

提出ソース

結果

問題	No.2682 Visible Divisible
ユーザー	ikoma
提出日時	2024-03-20 22:02:32
言語	Rust (1.77.0)
結果	TLE
実行時間	-
コード長	5,742 bytes
コンパイル時間	2,675 ms
コンパイル使用メモリ	207,640 KB
実行使用メモリ	10,388 KB
最終ジャッジ日時	2024-03-20 22:02:44
合計ジャッジ時間	7,188 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	90 ms 6,676 KB
testcase_01	AC	87 ms 6,676 KB
testcase_02	AC	87 ms 6,676 KB
testcase_03	AC	88 ms 6,676 KB
testcase_04	TLE	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#![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<T>(mut a: T, mut b: T) -> T
where T: Copy + Default + PartialOrd + Rem<Output = T>
{
	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::<Vec<_>>()
        };

        ($next:expr, chars) => {
            read_value!($next, String).chars().collect::<Vec<char>>()
        };

        ($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<u64, u32> {
		let mut ret: HashMap<u64, u32> = 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
	}

}

yukicoder

結果

テストケース

ソースコード