题目描述

$1\leq\ i\leq\ j\leq\ N$ をみたす整数の組 $(i,j)$ であって、$GCD(i,j)\neq\ 1$ かつ $GCD(P_i,P_j)\neq\ 1$ をみたすものの個数を求めてください。
ただし、正整数 $x$, $y$ に対して、$GCD(x,y)$ で $x$ と $y$ の最大公約数を表します。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

给你一个长度为 $N$ 的排列 $P=(P_1,P_2,...,P_N)$，你需要求出有多少 $(i,j)$ 满足 $1\leq i \leq j \leq N,\gcd(i,j)\ne 1,\gcd(P_i,P_j)\ne 1$。

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)$ の並び替えである。
• 入力は全て整数である。

Sample Explanation 1

条件をみたす組は $(3,3)$, $(3,6)$, $(4,4)$, $(4,6)$, $(5,5)$, $(6,6)$ の $6$ つです。 よって、 $6$ を出力します。