GCD Permutation

题目描述

给定一个从 $1$ 到 $N$ 的整数的置换 $P=(P_1,P_2,\ldots,P_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$ 的最大公约数。

输入格式

输入按照下列格式从标准输入给出： $N$ $P_1$ $P_2$ $\ldots$ $P_N$

输出格式

输出答案。

6
5 1 3 2 4 6

6

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

32

提示

$1 \leq N \leq 2\times 10^5$ $(P_1,P_2,\ldots,P_N)$ 是 $(1,2,\ldots,N)$ 的一个置换。 输入中的所有数值都是整数。有六对 $(3,3)$、$(3,6)$、$(4,4)$、$(4,6)$、$(5,5)$、$(6,6)$ 满足条件，因此应输出 $6$。

标签: AtCoder|abc230G

来源

AtCoder|abc230G