結果
| 問題 | No.1946 ロッカーの問題 |
| ユーザー |
 atcoder8
|
| 提出日時 | 2022-09-09 08:00:24 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 80 ms / 3,000 ms |
| コード長 | 7,132 bytes |
| コンパイル時間 | 12,315 ms |
| コンパイル使用メモリ | 383,040 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-11-25 05:25:40 |
| 合計ジャッジ時間 | 13,597 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,816 KB |
| testcase_01 | AC | 1 ms
6,816 KB |
| testcase_02 | AC | 4 ms
6,820 KB |
| testcase_03 | AC | 69 ms
6,820 KB |
| testcase_04 | AC | 4 ms
6,816 KB |
| testcase_05 | AC | 6 ms
6,820 KB |
| testcase_06 | AC | 6 ms
6,816 KB |
| testcase_07 | AC | 5 ms
6,816 KB |
| testcase_08 | AC | 21 ms
6,816 KB |
| testcase_09 | AC | 55 ms
6,816 KB |
| testcase_10 | AC | 48 ms
6,820 KB |
| testcase_11 | AC | 2 ms
6,816 KB |
| testcase_12 | AC | 14 ms
6,820 KB |
| testcase_13 | AC | 0 ms
6,820 KB |
| testcase_14 | AC | 1 ms
6,816 KB |
| testcase_15 | AC | 1 ms
6,816 KB |
| testcase_16 | AC | 1 ms
6,816 KB |
| testcase_17 | AC | 39 ms
6,816 KB |
| testcase_18 | AC | 80 ms
6,820 KB |
ソースコード
use crate::atcoder8_library::eratosthenes_sieve::EratosthenesSieve;
fn main() {
let (n, _m) = {
let mut line = String::new();
std::io::stdin().read_line(&mut line).unwrap();
let mut iter = line.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
};
let aa = {
let mut line = String::new();
std::io::stdin().read_line(&mut line).unwrap();
line.split_whitespace()
.map(|x| x.parse::<usize>().unwrap())
.collect::<Vec<_>>()
};
let mut actual = vec![false; n + 1];
for &a in aa.iter() {
actual[a] = true;
}
let mut ans = 0_u32;
let mut lockers = vec![false; n + 1];
let sieve = EratosthenesSieve::new(n);
for i in (1..=n).rev() {
if lockers[i] == actual[i] {
ans += 1;
} else {
let divisors = sieve.create_divisors_list(i);
for d in divisors {
lockers[d] = !lockers[d];
}
}
}
println!("{}", ans);
}
pub mod atcoder8_library {
pub mod eratosthenes_sieve {
//! Implements the Sieve of Eratosthenes.
//!
//! Finds the smallest prime factor of each number placed on the sieve,
//! so it can perform Prime Factorization as well as Primality Test.
#[derive(Debug, Clone)]
pub struct EratosthenesSieve {
sieve: Vec<usize>,
}
impl EratosthenesSieve {
/// Constructs a Sieve of Eratosthenes.
///
/// # Arguments
///
/// * `upper_limit` - The largest number placed on the sieve.
///
/// # Examples
///
/// ```
/// use atcoder8_library::eratosthenes_sieve::EratosthenesSieve;
///
/// let sieve = EratosthenesSieve::new(27);
/// assert_eq!(sieve.prime_factorization(12), vec![(2, 2), (3, 1)]);
/// ```
pub fn new(upper_limit: usize) -> Self {
let mut sieve: Vec<usize> = (0..=upper_limit).collect();
for p in (2..).take_while(|&i| i * i <= upper_limit) {
if sieve[p] != p {
continue;
}
for i in ((p * p)..=upper_limit).step_by(p) {
if sieve[i] == i {
sieve[i] = p;
}
}
}
Self { sieve }
}
/// Returns the least divisor of `n`.
///
/// # Examples
///
/// ```
/// use atcoder8_library::eratosthenes_sieve::EratosthenesSieve;
///
/// let sieve = EratosthenesSieve::new(27);
/// assert_eq!(sieve.min_divisor(1), 1);
/// assert_eq!(sieve.min_divisor(2), 2);
/// assert_eq!(sieve.min_divisor(6), 2);
/// assert_eq!(sieve.min_divisor(11), 11);
/// assert_eq!(sieve.min_divisor(27), 3);
/// ```
pub fn min_divisor(&self, n: usize) -> usize {
assert_ne!(n, 0, "`n` must be at least 1.");
self.sieve[n]
}
/// Determines if `n` is prime.
///
/// # Examples
///
/// ```
/// use atcoder8_library::eratosthenes_sieve::EratosthenesSieve;
///
/// let sieve = EratosthenesSieve::new(27);
/// assert!(!sieve.is_prime(1));
/// assert!(sieve.is_prime(2));
/// assert!(!sieve.is_prime(6));
/// assert!(sieve.is_prime(11));
/// assert!(!sieve.is_prime(27));
/// ```
pub fn is_prime(&self, n: usize) -> bool {
n >= 2 && self.sieve[n] == n
}
/// Performs prime factorization of `n`.
///
/// The result of the prime factorization is returned as a
/// list of prime factor and exponent pairs.
///
/// # Examples
///
/// ```
/// use atcoder8_library::eratosthenes_sieve::EratosthenesSieve;
///
/// let sieve = EratosthenesSieve::new(27);
/// assert_eq!(sieve.prime_factorization(1), vec![]);
/// assert_eq!(sieve.prime_factorization(12), vec![(2, 2), (3, 1)]);
/// assert_eq!(sieve.prime_factorization(19), vec![(19, 1)]);
/// assert_eq!(sieve.prime_factorization(27), vec![(3, 3)]);
/// ```
pub fn prime_factorization(&self, n: usize) -> Vec<(usize, usize)> {
assert_ne!(n, 0, "`n` must be at least 1.");
let mut factors: Vec<(usize, usize)> = vec![];
let mut t = n;
while t != 1 {
let p = self.sieve[t];
if factors.is_empty() || factors.last().unwrap().0 != p {
factors.push((p, 1));
} else {
factors.last_mut().unwrap().1 += 1;
}
t /= p;
}
factors
}
/// Creates a list of divisors of `n`.
///
/// The divisors are listed in ascending order.
///
/// # Examples
///
/// ```
/// use atcoder8_library::eratosthenes_sieve::EratosthenesSieve;
///
/// let sieve = EratosthenesSieve::new(27);
/// assert_eq!(sieve.create_divisors_list(1), vec![1]);
/// assert_eq!(sieve.create_divisors_list(12), vec![1, 2, 3, 4, 6, 12]);
/// assert_eq!(sieve.create_divisors_list(19), vec![1, 19]);
/// assert_eq!(sieve.create_divisors_list(27), vec![1, 3, 9, 27]);
/// ```
pub fn create_divisors_list(&self, n: usize) -> Vec<usize> {
assert_ne!(n, 0, "`n` must be at least 1.");
let prime_factors = self.prime_factorization(n);
let mut divisors = vec![1];
let divisors_num: usize = prime_factors.iter().map(|&(_, e)| e + 1).product();
divisors.reserve(divisors_num - 1);
for (p, e) in prime_factors {
let mut add_divisors = vec![];
add_divisors.reserve(divisors.len() * e);
let mut mul = 1;
for _ in 1..=e {
mul *= p;
for &d in divisors.iter() {
add_divisors.push(d * mul);
}
}
divisors.append(&mut add_divisors);
}
divisors.sort_unstable();
divisors
}
}
}
}