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::*;
}
