当前没有测试数据。

G - GCD排列

得分：$600$ 分

问题描述

给定一个排列 $P=(P_1,P_2,\ldots,P_N)$，其中包含了从 $1$ 到 $N$ 的整数。

找出满足 $1\leq i\leq j\leq N$、$GCD(i,j)\neq 1$ 以及 $GCD(P_i,P_j)\neq 1$ 的整数对 $(i,j)$ 的个数。
这里，对于正整数 $x$ 和 $y$，$GCD(x,y)$ 表示 $x$ 和 $y$ 的最大公约数。

约束条件

• $1 \leq N \leq 2\times 10^5$
• $(P_1,P_2,\ldots,P_N)$ 是 $(1,2,\ldots,N)$ 的一个排列。
• 输入中的所有值都是整数。

输入

从标准输入中按以下格式给出输入：

$N$

$P_1$ $P_2$ $\ldots$ $P_N$

输出

输出答案。

6
5 1 3 2 4 6

6

满足条件的六个整数对为 $(3,3)$, $(3,6)$, $(4,4)$, $(4,6)$, $(5,5)$, $(6,6)$，因此应该输出 $6$。

12
1 2 3 4 5 6 7 8 9 10 11 12

32

满足条件的整数对共有 $32$ 对，例如 $(1,4)$, $(1,6)$, $(1,8)$, $(1,12)$, $(2,4)$, $(2,6)$, $(2,8)$, $(2,9)$, $(2,10)$, $(2,12)$, $(3,6)$, $(3,9)$, $(3,10)$, $(3,12)$, $(4,4)$, $(4,6)$, $(4,8)$, $(4,9)$, $(4,10)$, $(4,12)$, $(5,10)$, $(5,12)$, $(6,6)$, $(6,8)$, $(6,9)$, $(6,10)$, $(6,11)$, $(6,12)$, $(7,8)$, $(8,8)$, $(8,9)$, $(8,10)$, $(11,11)$。