結果
| 問題 | No.1946 ロッカーの問題 |
| ユーザー |
 atcoder8
|
| 提出日時 | 2022-09-09 07:26:18 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 207 ms / 3,000 ms |
| コード長 | 6,822 bytes |
| コンパイル時間 | 14,902 ms |
| コンパイル使用メモリ | 383,820 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-05-03 23:27:20 |
| 合計ジャッジ時間 | 17,298 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,816 KB |
| testcase_01 | AC | 0 ms
6,812 KB |
| testcase_02 | AC | 5 ms
6,816 KB |
| testcase_03 | AC | 156 ms
6,816 KB |
| testcase_04 | AC | 4 ms
6,940 KB |
| testcase_05 | AC | 8 ms
6,944 KB |
| testcase_06 | AC | 9 ms
6,944 KB |
| testcase_07 | AC | 8 ms
6,940 KB |
| testcase_08 | AC | 48 ms
6,944 KB |
| testcase_09 | AC | 137 ms
6,944 KB |
| testcase_10 | AC | 116 ms
6,940 KB |
| testcase_11 | AC | 5 ms
6,940 KB |
| testcase_12 | AC | 29 ms
6,940 KB |
| testcase_13 | AC | 1 ms
6,940 KB |
| testcase_14 | AC | 1 ms
6,940 KB |
| testcase_15 | AC | 1 ms
6,940 KB |
| testcase_16 | AC | 1 ms
6,940 KB |
| testcase_17 | AC | 96 ms
6,944 KB |
| testcase_18 | AC | 207 ms
6,940 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 {
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)> {
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> {
let mut divisors = vec![];
let prime_factors = self.prime_factorization(n);
let mut stack = vec![(vec![0; prime_factors.len()], 0, 1)];
while let Some((exps, skip, d)) = stack.pop() {
divisors.push(d);
for (i, &(p, e)) in prime_factors.iter().enumerate().skip(skip) {
if exps[i] < e {
let mut next_exps = exps.clone();
next_exps[i] += 1;
stack.push((next_exps, i, d * p));
}
}
}
divisors.sort_unstable();
divisors
}
}
}
}