Tekijät

warning: unused import: `rand::prelude::*`
 --> input/code.rs:1:5
  |
1 | use rand::prelude::*;
  |     ^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::collections::BTreeMap`
 --> input/code.rs:2:5
  |
2 | use std::collections::BTreeMap;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: method is never used: `len`
  --> input/code.rs:25:5
   |
25 |     fn len(&self) -> usize {
   |     ^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

warning: method is never used: `reduce`
   --> input/code.rs:115:5
    |
115 |     fn reduce(&self, a: u32) -> u32 {
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

use rand::prelude::*;
use std::collections::BTreeMap;
use std::io::BufRead;

#[derive(Clone, Copy, Debug)]
struct Svec {
    i: u8,
    data: [u32; 7],
}

impl Svec {
    fn new() -> Self {
        Self {
            i: 0,
            data: Default::default(),
        }
    }
    fn push(&mut self, v: u32) {
        self.data[self.i as usize] = v;
        self.i += 1;
    }
    fn is_empty(&self) -> bool {
        self.i == 0
    }
    fn len(&self) -> usize {
        self.i as usize
    }

    fn with_subsets<F: FnMut(&[u32])>(&self, f: F) {
        let mut f = f;
        let mut subset = [0u32; 7];
        for i1 in 0..self.i as usize {
            subset[0] = self.data[i1];
            f(&subset[0..1]);
            for i2 in i1 + 1..self.i as usize {
                subset[1] = self.data[i2];
                f(&subset[0..2]);
                for i3 in i2 + 1..self.i as usize {
                    subset[2] = self.data[i3];
                    f(&subset[0..3]);
                    for i4 in i3 + 1..self.i as usize {
                        subset[3] = self.data[i4];
                        f(&subset[0..4]);
                        for i5 in i4 + 1..self.i as usize {
                            subset[4] = self.data[i5];
                            f(&subset[0..5]);
                            for i6 in i5 + 1..self.i as usize {
                                subset[5] = self.data[i6];
                                f(&subset[0..6]);
                                for i7 in i6 + 1..self.i as usize {
                                    // TODO: Replace by if condition
                                    subset[6] = self.data[i7];
                                    f(&subset[0..7]);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

struct Sieve {
    // sieve: Vec<Option<NonZeroUsize>>,
    prime_factors: Vec<Svec>,
}

impl Iterator for Svec {
    type Item = u32;
    fn next(&mut self) -> Option<Self::Item> {
        if self.is_empty() {
            None
        } else {
            self.i -= 1;
            Some(self.data[self.i as usize])
        }
    }
}

impl Sieve {
    fn new(n: u32) -> Self {
        let mut prime_factors = vec![Svec::new(); n as usize + 1];
        for i in 2..=n {
            if prime_factors[i as usize].is_empty() {
                // Prime
                for j in (1..).take_while(|j| *j * i <= n) {
                    prime_factors[(j * i) as usize].push(i);
                }
            }
        }

        Self { prime_factors }
    }

    // fn factors(&self, a: usize) -> Vec<usize> {
    //     let mut a = a;
    //     let mut res = Vec::new();
    //     while a > 1 {
    //         if let Some(p) = self.sieve[a] {
    //             res.push(p.get());
    //             a /= p.get();
    //         }
    //     }
    //     res
    // }

    fn unique_factors(&self, a: u32) -> Svec {
        // let mut f = self.factors(a);
        // f.dedup();
        // f
        self.prime_factors[a as usize]
    }

    fn reduce(&self, a: u32) -> u32 {
        self.unique_factors(a).product()
    }
}

fn main() {
    let sieve = Sieve::new(1_000_000);

    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let mut lines = stdin.lines();

    let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    let input: Vec<_> = lines
        .next()
        .unwrap()
        .unwrap()
        .split_whitespace()
        .map(|v| v.parse().unwrap())
        .map(|v| sieve.unique_factors(v))
        .collect();

    // Fill the count table
    let mut counts = vec![0; 1_000_000];
    let mut orig_counts = vec![0; 1_000_000];
    let mut dedup_input = Vec::with_capacity(100_000);
    for v in input {
        v.with_subsets(|s| counts[s.iter().product::<u32>() as usize] += 1);
        let vp = v.product::<u32>() as usize;
        if orig_counts[vp] == 0 {
            dedup_input.push(v);
        }
        orig_counts[vp] += 1;
    }

    // Count pairs
    let mut res = 0;
    for v in dedup_input {
        let mut subres = 0;
        // println!(
        //     "Handling {}, multiplier {}",
        //     v.product::<u32>(),
        //     orig_counts[v.product::<u32>() as usize]
        // );
        v.with_subsets(|s| {
            let c = counts[s.iter().product::<u32>() as usize] - 1;
            // println!("Subset {:?}, count {}", s, c);
            if s.len() % 2 == 0 {
                subres -= c;
            } else {
                subres += c;
            }
        });

        res += orig_counts[v.product::<u32>() as usize] * subres;
    }

    println!("{}", n * (n - 1) / 2 - res / 2);

    // println!("{:?}", input);
    // for _ in 0..t {
    //     let c: usize = lines.next().unwrap().unwrap().parse().unwrap();
    //     if solve(c) {
    //         println!("YES");
    //     } else {
    //         println!("NO");
    //     }
    // }
}

#[cfg(test)]
mod tests {
    use super::*;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 2, 3

Verdict: ACCEPTED

Test 4

Group: 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: ACCEPTED

Test 6

Group: 3

Verdict: ACCEPTED

Test 7

Group: 3

Verdict: ACCEPTED