#CS2417. 计数互质数对

计数互质数对

题目背景

翻译自 CSES-2417 题。

题目描述

给定一个包含 n 个正整数的列表，任务是统计其中互质的数对的数量。即，求满足最大公约数为 1 的数对的数量。

输入格式

第一行包含一个整数 n：表示列表的大小。

第二行包含 n 个整数 x1,x2,…,xnx_1,x_2,…,x_nx1​,x2​,…,xn​：表示列表的内容。

输出格式

输出一个整数：表示满足条件的互质数对的数量。

样例

8
5 4 20 1 16 17 5 15

19

说明/提示

$1 \leq n \leq 10^5$

1≤xi≤1061 \leq x_i \leq 10^61≤xi​≤106。