#982386 (Rust) No.2758 RDQ

• 問題: No.2758 RDQ
• ユーザー: atcoder8
• 提出日時: 2024-05-17 22:40:06
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 192 ms / 2,000 ms
• コード長: 7,429 bytes
• コンパイル時間: 13,214 ms
• コンパイル使用メモリ: 402,144 KB
• 実行使用メモリ: 29,184 KB
• 最終ジャッジ日時: 2024-05-17 23:46:07
• 合計ジャッジ時間: 17,334 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	118 ms; 14,396 KB
testcase_01	AC	4 ms; 6,940 KB
testcase_02	AC	4 ms; 6,940 KB
testcase_03	AC	4 ms; 6,944 KB
testcase_04	AC	4 ms; 6,940 KB
testcase_05	AC	4 ms; 6,944 KB
testcase_06	AC	188 ms; 28,928 KB
testcase_07	AC	192 ms; 29,184 KB
testcase_08	AC	189 ms; 29,056 KB
testcase_09	AC	189 ms; 29,044 KB
testcase_10	AC	189 ms; 29,184 KB
testcase_11	AC	141 ms; 15,488 KB
testcase_12	AC	144 ms; 15,488 KB
testcase_13	AC	147 ms; 15,488 KB
testcase_14	AC	144 ms; 15,360 KB
testcase_15	AC	146 ms; 15,360 KB
testcase_16	AC	142 ms; 15,232 KB
testcase_17	AC	144 ms; 15,232 KB
testcase_18	AC	148 ms; 15,616 KB
testcase_19	AC	148 ms; 15,360 KB
testcase_20	AC	143 ms; 15,360 KB
testcase_21	AC	4 ms; 6,940 KB
testcase_22	AC	4 ms; 6,940 KB
testcase_23	AC	4 ms; 6,944 KB

ソースコード

use proconio::{input, marker::Usize1};

use crate::eratosthenes_sieve::EratosthenesSieve;

const MAX: usize = 10_usize.pow(5);

fn main() {
    input! {
        (n, q): (usize, usize),
        aa: [usize; n],
        lrk: [(Usize1, usize, usize); q],
    }

    let sieve = EratosthenesSieve::new(MAX);

    let mut positions_by_divisor = vec![vec![]; MAX + 1];
    for (i, &a) in aa.iter().enumerate() {
        let divisors = sieve.divisors(a);
        for &divisor in &divisors {
            positions_by_divisor[divisor].push(i);
        }
    }

    for &(l, r, k) in &lrk {
        let positions = &positions_by_divisor[k];
        let left = positions.partition_point(|&pos| pos < l);
        let right = positions.partition_point(|&pos| pos < r);

        println!("{}", right - left);
    }
}

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 prime factor of `n`.
        ///
        /// However, if `n` is `1`, then `1` is returned.
        ///
        /// # Examples
        ///
        /// ```
        /// use atcoder8_library::eratosthenes_sieve::EratosthenesSieve;
        ///
        /// let sieve = EratosthenesSieve::new(27);
        /// assert_eq!(sieve.get_least_prime_factor(1), 1);
        /// assert_eq!(sieve.get_least_prime_factor(2), 2);
        /// assert_eq!(sieve.get_least_prime_factor(6), 2);
        /// assert_eq!(sieve.get_least_prime_factor(11), 11);
        /// assert_eq!(sieve.get_least_prime_factor(27), 3);
        /// ```
        pub fn get_least_prime_factor(&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 n = n;

            let mut factors: Vec<(usize, usize)> = vec![];

            while n != 1 {
                let p = self.sieve[n];

                if factors.is_empty() || factors.last().unwrap().0 != p {
                    factors.push((p, 1));
                } else {
                    factors.last_mut().unwrap().1 += 1;
                }

                n /= p;
            }

            factors
        }

        /// Creates a list of positive divisors of `n`.
        ///
        /// The positive divisors are listed in ascending order.
        ///
        /// # Examples
        ///
        /// ```
        /// use atcoder8_library::eratosthenes_sieve::EratosthenesSieve;
        ///
        /// let sieve = EratosthenesSieve::new(27);
        /// assert_eq!(sieve.create_divisor_list(1), vec![1]);
        /// assert_eq!(sieve.create_divisor_list(12), vec![1, 2, 3, 4, 6, 12]);
        /// assert_eq!(sieve.create_divisor_list(19), vec![1, 19]);
        /// assert_eq!(sieve.create_divisor_list(27), vec![1, 3, 9, 27]);
        /// ```
        pub fn divisors(&self, n: usize) -> Vec<usize> {
            assert_ne!(n, 0, "`n` must be at least 1.");

            let prime_factors = self.prime_factorization(n);
            let divisor_num: usize = prime_factors.iter().map(|&(_, exp)| exp + 1).product();

            let mut divisors = vec![1];
            divisors.reserve(divisor_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
        }

        /// Calculates the number of positive divisors of `n`.
        ///
        /// # Examples
        ///
        /// ```
        /// use atcoder8_library::eratosthenes_sieve::EratosthenesSieve;
        ///
        /// let sieve = EratosthenesSieve::new(27);
        /// assert_eq!(sieve.calc_divisor_num(1), 1);
        /// assert_eq!(sieve.calc_divisor_num(12), 6);
        /// assert_eq!(sieve.calc_divisor_num(19), 2);
        /// assert_eq!(sieve.calc_divisor_num(27), 4);
        /// ```
        pub fn calc_divisor_num(&self, n: usize) -> usize {
            assert_ne!(n, 0, "`n` must be at least 1.");

            let mut n = n;

            let mut divisor_num = 1;
            let mut cur_p = None;
            let mut cur_exp = 0;

            while n != 1 {
                let p = self.sieve[n];

                if Some(p) == cur_p {
                    cur_exp += 1;
                } else {
                    divisor_num *= cur_exp + 1;

                    cur_p = Some(p);
                    cur_exp = 1;
                }

                n /= p;
            }

            divisor_num *= cur_exp + 1;

            divisor_num
        }
    }
}